제출 #173255

#제출 시각아이디문제언어결과실행 시간메모리
173255dndhkAliens (IOI16_aliens)C++14
12 / 100
113 ms388 KiB
#include "aliens.h" #include <bits/stdc++.h> #define all(v) (v).begin(), (v).end() #define sortv(v) sort(all(v)) #define uniqv(v) (v).erase(unique(all(v)), (v).end()) #define pb push_back #define FI first #define SE second #define lb lower_bound #define ub upper_bound #define mp make_pair #define test 0 #define TEST if(test) using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; const int MOD = 1000000007; // 998244353 const int INF = 2e9; const ll INFLL = 1e15; const int MAX_N = 4000; int N, M, K; vector<pii> vt; vector<ll> C; ll dp[2][MAX_N+1]; long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { N = n; M = m; K = k; for(int i=0; i<N; i++){ vt.pb({min(r[i], c[i]), max(r[i], c[i]) + 1}); } sort(vt.begin(), vt.end()); int mx = -1; for(int i=0 ;i<N; i++){ if(mx>=vt[i].second){ vt[i].second = INF; vt[i].first = INF; }else mx = max(mx, vt[i].second); } mx = M+1; for(int i=N-1; i>=0; i--){ if(vt[i].first==INF && vt[i].second==INF) continue; if(mx<=vt[i].first){ vt[i].first = INF; vt[i].second = INF; }else mx = min(mx, vt[i].first); } sort(vt.begin(), vt.end()); while(!vt.empty() && vt.back().first==INF && vt.back().second==INF) vt.pop_back(); TEST{ for(int i=0; i<vt.size(); i++){ cout<<vt[i].first<<" "<<vt[i].second<<endl; } } for(int i=0; i<=vt.size(); i++){ dp[0][i] = dp[1][i] = INFLL; } C.pb(0LL); for(int i=1; i<vt.size(); i++){ C.pb(max(0LL, (ll)(vt[i-1].second - vt[i].first)) * max(0LL, (ll)(vt[i-1].second - vt[i].first))); } dp[0][0] = dp[1][0] = 0LL; while(K--){ dp[1][0] = 0LL; for(int i=0; i<vt.size(); i++){ for(int j=0; j<=i; j++){ dp[1][i+1] = min(dp[1][i+1], dp[0][j] + (ll)(vt[i].second - vt[j].first) * (ll)(vt[i].second - vt[j].first) + C[j]); } } for(int i=0; i<=vt.size(); i++){ TEST cout<<dp[1][i]<<" "; dp[0][i] = dp[1][i]; dp[1][i] = INFLL; } TEST cout<<endl; } return dp[0][vt.size()]; }

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

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:57:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<vt.size(); i++){
                ~^~~~~~~~~~
aliens.cpp:61:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<=vt.size(); i++){
               ~^~~~~~~~~~~
aliens.cpp:65:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<vt.size(); i++){
               ~^~~~~~~~~~
aliens.cpp:71:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<vt.size(); i++){
                ~^~~~~~~~~~
aliens.cpp:76:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<=vt.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...