提出 #68924482

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
#include <queue>
const int maxn=1010;
typedef long long ll;
const ll inf=3e9;
#define MP make_pair
struct edge { int v,nxt; ll w,cost; } c[5000000];
ll d[maxn],base;
int SS,TT;
int head[maxn],edge_cnt,cur[maxn],S,T,node_cnt,q[maxn*maxn],hd,tl;
void addedge(int u,int v,ll w,ll cost) {
	c[++edge_cnt]=(edge){v,head[u],w,cost}; head[u]=edge_cnt;
	c[++edge_cnt]=(edge){u,head[v],0,-cost}; head[v]=edge_cnt;
}
void addedge(int u,int v,ll l,ll r,ll cost) {
    addedge(u,v,r-l,cost);
    d[v]+=l,d[u]-=l;
    base+=cost*l;
}
ll dep[maxn]; bool inq[maxn];
void init() { for (int i=0;i<=node_cnt;i++) head[i]=0; edge_cnt=1; }
bool bfs() {
    for (int i=0;i<=node_cnt;i++) dep[i]=inf,cur[i]=head[i],inq[i]=0;
	q[hd=tl=1]=S,dep[S]=0;
	while (hd<=tl) {
		int x=q[hd++]; inq[x]=0;
		for(int i=head[x];i;i=c[i].nxt) {
			if (c[i].w&&dep[c[i].v]>dep[x]+c[i].cost) {
				dep[c[i].v]=dep[x]+c[i].cost;
				if (!inq[c[i].v]) inq[c[i].v]=true,q[++tl]=c[i].v;
			} } }
	return dep[T]<inf; }
ll dfs(int x,ll flow) {
	if (x==T||!flow) return flow;
	inq[x]=1; int f=0,rf;
	for(int &i=cur[x];i;i=c[i].nxt) {
		if (!inq[c[i].v]&&dep[c[i].v]==dep[x]+c[i].cost
		&&(rf=dfs(c[i].v,min(flow,c[i].w)))) {
			flow-=rf,f+=rf;
			c[i].w-=rf,c[i^1].w+=rf;
			if(!flow) return f;
		} }
	return f;
}
pair<ll,ll> MCMF() {
	ll ans=0,res=0;
	while (bfs()) {
		ll tmp=dfs(S,inf);
        // if (dep[T]>0) break;
        ans+=tmp;
        res+=dep[T]*tmp;
	}
	return MP(ans,res+base);
}
void sol() {
	SS=++node_cnt,TT=++node_cnt;
	for(int i=1;i<=node_cnt-2;i++){
		if (d[i]>0) addedge(SS,i,d[i],0);
		else addedge(i,TT,-d[i],0);
		d[i]=0;
	}
	addedge(T,S,inf,0);
	S=SS,T=TT;
} // init() -> set cnt -> add_edge -> sol()
int n,m,a[maxn],b[maxn];

int main() {
    scanf("%d %d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1;i<=n;i++) b[i]=a[i]-a[i-1];
    S=n+2,T=S+1;
    node_cnt=T;
    init();
    ll all=0;
    for (int i=1;i<=n;i++) {
        if (b[i]<0) addedge(S,i,-b[i],inf,0),all-=b[i];
        else addedge(i,T,0,b[i],0);
    }
    for (int i=1;i<=m;i++) {
        int x,y; scanf("%d %d",&x,&y);
        y++;
        addedge(x,y,inf,1);
    }
    addedge(n+1,T,inf,0);
    sol();
    pair<ll,ll> res=MCMF();
    if (all!=res.first) puts("-1");
    else printf("%lld\n",res.second);
    // printf("%lld %lld %lld\n",all,res.first,res.second);
    return 0;
}

提出情報

コンパイルエラー

Main.cpp: In function ‘int main()’:
Main.cpp:69:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   69 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
Main.cpp:70:33: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   70 |     for (int i=1;i<=n;i++) scanf("%d",&a[i]);
      |                            ~~~~~^~~~~~~~~~~~
Main.cpp:81:23: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   81 |         int x,y; scanf("%d %d",&x,&y);
      |                  ~~~~~^~~~~~~~~~~~~~~

ジャッジ結果