제출 #69224

#제출 시각아이디문제언어결과실행 시간메모리
69224NavickAliens (IOI16_aliens)C++17
60 / 100
514 ms22244 KiB
#include <bits/stdc++.h> #include "aliens.h" #define F first #define S second #define pii pair<int, int> #define pb push_back #define pll pair<ll, ll> using namespace std; typedef long long ll; const int maxN = 5e4 + 10, maxK = 510; const ll oo = 2e15; ll las[maxN], dp[maxN], f[maxN]; int l[maxN], r[maxN]; vector <pii> que; pll lines[maxN]; int sz = 0; bool cmp(pii a1, pii a2) { if(a1.F != a2.F) return a1.F < a2.F; return a1.S > a2.S; } ll barkhord(pll A, pll B) { return (B.F - A.F + A.S - B.S - 1) / (A.S - B.S); } long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { if(n > maxN) return cout << 1/0 << endl, -1; for (int i=0; i<n; i++) { if(r[i] <= c[i]) c[i] ++; else r[i] ++; que.pb({min(r[i], c[i]), max(r[i], c[i])}); } sort(que.begin(), que.end(), cmp); int mx = -1, cnt = 0; for (int i=0; i<n; i++) { if(mx >= que[i].S) continue ; else { l[cnt] = que[i].F, r[cnt] = que[i].S; mx = max(mx, que[i].S); cnt ++; } } n = cnt; //for (int i=0; i<n; i++) cout << l[i] << ',' << r[i] << endl; for (int i=0; i<=n; i++) las[i] = oo; las[0] = 0; for (int i=0; i<n-1; i++) if(r[i] > l[i + 1]) f[i] = 1LL * (r[i] - l[i + 1]) * (r[i] - l[i + 1]); for (int j=1; j<=k; j++) { dp[0] = 0; sz = 0; int ptr = 0; //cout << j << " --> " << endl; for (int i=1; i<=n; i++) { ll c = 0; if(i - 1 > 0) c = f[i - 2]; if(las[i - 1] < oo) { pll t = {las[i - 1] - c + (ll)l[i - 1] * l[i - 1], -2LL * l[i - 1]}; while(sz >= 2 && barkhord(lines[sz - 2], lines[sz - 1]) >= barkhord(lines[sz - 1], t)) sz--; lines[sz ++] = t; } /*if(j == 2) { cout << sz << " lines " << endl; for (int c=0; c<sz; c++) cout << lines[c].F << ',' << lines[c].S << endl; }*/ ptr = min(ptr, sz - 1); while(ptr < sz - 1 && barkhord(lines[ptr], lines[ptr + 1]) <= r[i - 1]) ptr ++; // cout << ptr << endl; dp[i] = lines[ptr].F + (ll)r[i - 1] * r[i - 1] + (ll)r[i - 1] * lines[ptr].S; //cout << i << " : " << dp[i]; cout << endl << endl; } for (int i=1; i<=n; i++) las[i] = dp[i]; } return dp[n]; }

컴파일 시 표준 에러 (stderr) 메시지

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:37:31: warning: division by zero [-Wdiv-by-zero]
  if(n > maxN) return cout << 1/0 << endl, -1;
                              ~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...