Submission #760670

#TimeUsernameProblemLanguageResultExecution timeMemory
760670AryanReddyAliens (IOI16_aliens)C++14
Compilation error
0 ms0 KiB
#undef local #include <bits/stdc++.h> #define all(v) v.begin(),v.end() #define allr(v) v.rbegin(),v.rend() #define fori(i,n) for(int i=0;i<n;i++) #define ford(i,n) for(int i = n-1;i >= 0;i--) #define pb push_back #define ll long long int //#define mod 998244353 #define pi pair<int,int> #define pll pair<ll,ll> #define mp make_pair #define fi first #define se second #define printVector(v) fori(;,v.size()) {cout << v[i] << " ";} cout << "\n"; #pragma GCC optimize("O3") std::mt19937 rng((unsigned int) std::chrono::steady_clock::now().time_since_epoch().count()); using namespace std; struct LineContainer{ vector<pll> lines; void add(ll k,ll m){ lines.pb({k,m}); } ll get(ll x){ ll res = 1e18; for(auto p:lines){ res = min(res,p.fi * x + p.se); } return res; } }; ll getAns(vector<pll> a,ll k){ int n = a.size(); sort(all(a),[&](pll x,pll y){ return mp(x.fi,-x.se) < mp(y.fi,-y.se); }); int ptr = a[0].se; vector<pll> b = {a[0]}; for(int i= 1;i < n;i++){ if(a[i].se <= ptr){ continue; } b.push_back(a[i]); ptr = a[i].se; } a = b; n = a.size(); vector<vector<ll> > dp(n+1,vector<ll> (k+1,1e18)); vector<LineContainer> L(k+1); fori(i,k+1) dp[0][i] = 0; for(int j = 0;j < k;j++){ ll lt1 = a[0].fi; ll c = - 2 * lt1 + lt1 * lt1; ll a = -2 * lt1; L[j+1].add(a,c); } for(int i = 1;i <= n;i++){ for(int j = 1;j <= k;j++){ dp[i][j] = dp[i][j-1]; ll ri=a[i-1].se; dp[i][j] = min(dp[i][j],L[j].get(ri) + ri * ri + 2*ri + 1); if(j < k && i < n){ ll lt1 = a[i].fi; ll c = dp[i][j] - 2 * lt1 + lt1 * lt1; ll rt = a[i-1].se; ll tmp = max(0ll,rt - lt1 + 1); c -= tmp * tmp; ll a = -2 * lt1; L[j+1].add(a,c); } } } return dp[n][k]; } long long take_photos(int n, int m, int k, vector<int> r, vector<int> c){ vector<pll> a; for(int i = 0;i < n;i++){ int x = r[i]; int y = c[i]; a.pb(mp(min(x,y),max(x,y))); } sort(all(a)); a.erase(unique(all(a)),a.end()); ll ans = getAns(a,k); return ans; } int main(){ int n,m,k; cin >> n >> m >> k; vector<int> r(n),c(n); fori(i,n) cin >> r[i] >> c[i]; cout << take_photos(n,m,k,r,c) << "\n"; }

Compilation message (stderr)

/usr/bin/ld: /tmp/ccyi2WEH.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccnxp04I.o:aliens.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status