제출 #67173

#제출 시각아이디문제언어결과실행 시간메모리
67173TalantAliens (IOI16_aliens)C++17
12 / 100
188 ms6600 KiB
#include "aliens.h" //#include "grader.cpp" #include <bits/stdc++.h> #define mk make_pair #define sc second #define fr first #define pb push_back using namespace std; const long long N = (1e6 + 5); const long long inf = (1e9 + 7); pair<long long,long long> dp[1005][1005]; long long a[1005][1005]; long long cn = 0; long long u[N]; long long mn; long long ans = inf; vector <long long> v; long long f (long long mn,long long i,long long j,long long k) { if (mn > v[j]) return 0; return ((v[j] - max(mn,dp[j][k - 1].sc) + 1) * (v[j] - max(mn,dp[j][k - 1].sc) + 1)); } long long take_photos(int n, int m, int kk, vector<int> r, vector<int> c) { for (long long i = 0; i < m; i ++) u[i] = -1; for (long long i = 0; i < n; i ++) { if (u[max(r[i],c[i])] == -1) v.pb(max(r[i],c[i])),u[max(r[i],c[i])] = min(r[i],c[i]); else u[max(r[i],c[i])] = min(u[max(r[i],c[i])],(long long)min(r[i],c[i])); } sort (v.begin(),v.end()); for (long long i = 0; i < v.size(); i ++) for (long long k = 1; k <= kk; k ++) dp[i][k].fr = dp[i][k].sc = inf; mn = u[v[0]]; for (long long i = 0; i < v.size(); i ++) { mn = min(mn,u[v[i]]); dp[i][1].fr = (v[i] - mn + 1) * (v[i] - mn + 1); dp[i][1].sc = v[i]; } for (long long k = 2; k <= kk; k ++) { for (long long i = 0; i < v.size(); i ++) { mn = u[v[i]]; for (long long j = i - 1; j >= 0; j --) { if (dp[j][k - 1].fr + (v[i] - mn + 1) * (v[i] - mn + 1) - f(mn,i,j,k) < dp[i][k].fr) dp[i][k].fr = dp[j][k - 1].fr + (v[i] - mn + 1) * (v[i] - mn + 1) - f(mn,i,j,k),dp[i][k].sc = mn; mn = min(mn,u[v[j]]); } } } for (long long i = 1; i <= kk; i ++) ans = min(ans,dp[(long long)v.size() - 1][i].fr); return ans; }

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

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:39:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (long long i = 0; i < v.size(); i ++)
                             ~~^~~~~~~~~~
aliens.cpp:44:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (long long i = 0; i < v.size(); i ++) {
                             ~~^~~~~~~~~~
aliens.cpp:51:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (long long i = 0; i < v.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...