Submission #35077835

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/mincostflow>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;}

int main(){
  int n = read(); // 3e4
  const int N = 150;
  const int S = N*2;
  const int T = S+1;
  atcoder::mcf_graph<ll,ll> g(T+1);
  rep(i,0,N) g.add_edge(S,i,1,0);
  rep(i,0,N) g.add_edge(N+i,T,1,0);
  ll MAX = 1e9;
  rep(i,0,n){
    int a = read()-1;
    int b = read()-1 + N;
    int c = read();
    g.add_edge(a,b,1,MAX-c);
  }
  auto points = g.slope(S,T); // 包含{0,0}
  vector<pair<ll,ll>> ans;
  for(auto [f1,c1]:points){
    if(ans.size() != 0 && ans.back().first+1 != f1){
      auto [f0,c0] = ans.back();
      rep(f,f0+1,f1) ans.push_back({f,c0 + (c1-c0)/(f1-f0)*(f-f0)}); // [f0+1..f1-1]
    }
    ans.push_back({f1,c1});
  }
  printf("%d\n",(int)ans.size()-1);
  rep(i,1,ans.size()) printf("%lld\n",MAX*ans[i].first - ans[i].second);
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘ll read()’:
./Main.cpp:10:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   10 | ll read(){ll r;scanf("%lld",&r);return r;}
      |                ~~~~~^~~~~~~~~~~

Judge Result