제출 #401839

#제출 시각아이디문제언어결과실행 시간메모리
401839peuchAliens (IOI16_aliens)C++17
25 / 100
2078 ms87404 KiB
#include "aliens.h" #include<bits/stdc++.h> using namespace std; const int MAXN = 4e3 + 10; const int MAXM = 1e6 + 10; const long long INF = 1e18; long long dp[MAXN][MAXN]; int seg[4 * MAXM]; struct interval{ int l, r; interval(int _l = 0, int _r = 0){ l = _l, r = _r; if(l > r) swap(l, r); } bool operator < (interval a){ if(r == a.r) return l > a.l; return r < a.r; } }; void build(int pos, int ini, int fim){ seg[pos] = -1; if(ini == fim) return; int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1; build(e, ini, mid); build(d, mid + 1, fim); } void update(int pos, int ini, int fim, int p, int q, int val){ if(ini > q || fim < p) return; if(ini >= p && fim <= q){ seg[pos] = max(seg[pos], val); return; } int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1; update(e, ini, mid, p, q, val); update(d, mid + 1, fim, p, q, val); } int query(int pos, int ini, int fim, int id){ if(ini > id || fim < id) return -1; if(ini == fim) return seg[pos]; int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1; return max(seg[pos], max(query(e, ini, mid, id), query(d, mid + 1, fim, id))); } long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { vector<interval> ord (n); for(int i = 0; i < n; i++) ord[i] = interval(r[i], c[i]); sort(ord.begin(), ord.end()); int minL = m; for(int i = 0; i < n; i++){ minL = min(minL, ord[i].l); dp[i][0] = (long long)(ord[i].r - minL + 1) * (ord[i].r - minL + 1); } int lAux[n][n]; build(1, 0, m); for(int i = 0; i < n; i++){ for(int j = 0; j <= i; j++) lAux[j][i] = query(1, 0, m, ord[j].l); update(1, 0, m, ord[i].l + 1, m, i); } for(int j = 1; j < k; j++){ for(int i = 0; i < n; i++){ dp[i][j] = dp[i][j - 1]; for(int l = 0; l <= i; l++){ if(ord[l].l > ord[i].l) continue; int h = lAux[l][i]; long long quad = (long long) (ord[i].r - ord[l].l + 1) * (ord[i].r - ord[l].l + 1); long long minus = ((h < 0 || ord[h].r < ord[l].l) ? 0 : ((long long) (ord[h].r - ord[l].l + 1) * (ord[h].r - ord[l].l + 1))); long long aux = quad + ((h < 0) ? 0 : dp[h][j - 1] - minus); dp[i][j] = min(dp[i][j], aux); } } } return dp[n - 1][k - 1]; }

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

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:64:6: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   64 |      for(int j = 0; j <= i; j++)
      |      ^~~
aliens.cpp:66:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   66 |   update(1, 0, m, ord[i].l + 1, m, i);
      |   ^~~~~~
#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...