제출 #743826

#제출 시각아이디문제언어결과실행 시간메모리
743826baojiaopisuAliens (IOI16_aliens)C++14
25 / 100
91 ms8860 KiB
#include "aliens.h" #include<bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; using pii = pair<int, int>; using pll = pair<ll, ll>; using pld = pair<ld, ld>; #define fi first #define se second #define left BAO #define right ANH #define pb push_back #define pf push_front #define mp make_pair #define ins insert #define btpc __builtin_popcount #define btclz __builtin_clz #define sz(x) (int)(x.size()); #define all(x) x.begin(), x.end() #define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] " mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1}; int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1}; int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1}; template<class X, class Y> bool minimize(X &x, const Y &y) { if (x > y) { x = y; return true; } return false; } template<class X, class Y> bool maximize(X &x, const Y &y) { if (x < y) { x = y; return true; } return false; } const int MOD = 1e9 + 7; //998244353 template<class X, class Y> void add(X &x, const Y &y) { x = (x + y); if(x >= MOD) x -= MOD; } template<class X, class Y> void sub(X &x, const Y &y) { x = (x - y); if(x < 0) x += MOD; } /* Author : Le Ngoc Bao Anh, 12A5, LQD High School for Gifted Student*/ const ll INF = 1e18; const ll LIM = 1e14; const int N = 1e6 + 10; ll dp[505][505]; int Lopt[505][505], Ropt[505][505]; ll g[N]; ll take_photos(int n, int m, int k, vector<int> x, vector<int> y) { vector<pii> point, npoint; for(int i = 0; i < m; i++) g[i] = INF; for(int i = 0; i < n; i++) { if(y[i] > x[i]) swap(x[i], y[i]); minimize(g[x[i]], y[i]); } for(int i = 0; i < m; i++) if(g[i] <= m) point.pb({i, g[i]}); sort(all(point)); ll D = INF; for(int i = point.size() - 1; i >= 0; i--) { if(point[i].se >= D) continue; npoint.pb(point[i]); D = point[i].se; } point = npoint; sort(all(point)); for(int i = 0; i <= point.size(); i++) { for(int j = 0; j <= k; j++) dp[i][j] = INF, Lopt[i][j] = Ropt[i][j] = -1; } ll ans = INF; for(int i = 0; i < point.size(); i++) { if(i == 0) { ll d = (point[i].fi - point[i].se + 1); dp[i][1] = d * d; if(i == point.size() - 1) minimize(ans, d * d); continue; } for(int j = 1; j <= min(k, i + 1); j++) { for(int t = i; t >= 0; t--) { ll d = point[i].fi - point[i].se + 1 + point[i].se - point[t].se; ll cost = d * d; if(t > 0) { if(point[t - 1].fi >= point[t].se) { ll d = point[t - 1].fi - point[t].se + 1; cost -= d * d; } cost += dp[t - 1][j - 1]; } if(minimize(dp[i][j], cost)) { if(Ropt[i][j] == -1) Ropt[i][j] = t; Lopt[i][j] = t; } if(i == point.size() - 1) minimize(ans, cost); } } } for(int i = 0; i < point.size(); i++) { for(int j = 0; j < k; j++) { if(dp[i][j] >= LIM || dp[i][j + 1] >= LIM) continue; assert(Lopt[i][j] <= Ropt[i][j + 1]); } // for(int j = 0; j <= k; j++) { // if(i == 0 || dp[i][j] >= LIM || dp[i - 1][j] >= LIM) continue; // assert(Ropt[i - 1][j] <= Lopt[i][j]); // } } return ans; }

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

aliens.cpp: In function 'll take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:100:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  for(int i = 0; i <= point.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~
aliens.cpp:105:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |  for(int i = 0; i < point.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~
aliens.cpp:109:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |    if(i == point.size() - 1) minimize(ans, d * d);
      |       ~~^~~~~~~~~~~~~~~~~~~
aliens.cpp:128:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     if(i == point.size() - 1) minimize(ans, cost);
      |        ~~^~~~~~~~~~~~~~~~~~~
aliens.cpp:133:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |  for(int i = 0; i < point.size(); 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...