제출 #931198

#제출 시각아이디문제언어결과실행 시간메모리
931198arnold518수열 (APIO14_sequence)C++17
컴파일 에러
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; namespace Alien { // MAXN must be defined const int MAXN = 5e5; int N; // dp[i] : optimal dp value of i // cnt[i] : how much transitions were used in optimal dp[i] // memo[i] : previous transition position from i // V : restored optimal solution ll dp[MAXN+10]; int cnt[MAXN+10], memo[MAXN+10]; vector<int> V; void init(int _N) { N=_N; } // For given lambda, calculate dp, cnt, memo, V // dp[i] = min(or max)_{j<i} (dp[j] + cost(j, i)*2 - lambda) void solve(ll lambda) { // initialize dp, cnt, memo, V, (other data structures) for(int i=0; i<=N; i++) dp[i]=cnt[i]=memo[i]=0; V.clear(); for(int i=1; i<=N; i++) { // get_opt(i), cost(p, q) must be implemented // opt = argmin(or max)_{j<i} (dp[j] + cost(j, i)*2) // your code goes here int opt = 0; for(int j=0; j<i; j++) if(dp[opt]+(ll)(i-opt)*(i-opt)*2 > dp[j]+(ll)(i-j)*(i-j)*2) opt=j; dp[i] = dp[opt] + (ll)(i-opt)*(i-opt)*2 - lambda; // Don't forget *2 cnt[i] = cnt[opt]+1; memo[i] = opt; } for(int i=N; i>0;) { V.push_back(i); i=memo[i]; } V.push_back(0); reverse(V.begin(), V.end()); } // Get optimal dp[N][K] for given K // Returns (answer, restored solution) // dp[i][k] = min(or max)_{j<i} (dp[j][k-1] + cost(j, i)) pair<ll, vector<int>> alien(int K) { // lambda equals slope // minimum : K increase, lambda increase // maximum : k increase, lambda decrease ll lo=-1e18, hi=1e18; // range for lambda is [2*lo+1, 2*hi+1] while(lo+1<hi) { ll mid=lo+hi>>1; solve(2*mid+1); if(K <= cnt[N]) hi=mid; // min : <= , max : >= else lo=mid; } vector<int> P1, P2, ansV; solve(2*lo+1); P1=V; solve(2*hi+1); P2=V; if(P1.size()>P2.size()) swap(P1, P2); if(P1.size()-1==K) ansV=P1; else if(P2.size()-1==K) ansV=P2; else { assert(P1.size()-1<K && K<P2.size()-1); int x=K+1-P1.size(); for(int i=0; i+1<P1.size() && i+x+1<P2.size(); i++) { if(P1[i]<=P2[i+x] && P2[i+x+1]<=P1[i+1]) { for(int j=0; j<=i+x; j++) ansV.push_back(P2[j]); for(int j=i+1; j<P1.size(); j++) ansV.push(P1[j]); } } } assert(ansV.size()==K+1); solve(2*hi); ll ans=dp[N]/2+hi*K; return {ans, ansV}; } } void test_alien() { // min, cost(j, i) = (i-j)*(i-j) Alien::init(15); auto [ans, ansV] = Alien::alien(4); assert(ans == 57 && ansV == vector<int>({0, 3, 7, 11, 15})); } int main() { test_alien(); }

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

sequence.cpp: In function 'std::pair<long long int, std::vector<int> > Alien::alien(int)':
sequence.cpp:68:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |             ll mid=lo+hi>>1;
      |                    ~~^~~
sequence.cpp:79:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   79 |         if(P1.size()-1==K) ansV=P1;
      |            ~~~~~~~~~~~^~~
sequence.cpp:80:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   80 |         else if(P2.size()-1==K) ansV=P2;
      |                 ~~~~~~~~~~~^~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from sequence.cpp:1:
sequence.cpp:83:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   83 |             assert(P1.size()-1<K && K<P2.size()-1);
      |                    ~~~~~~~~~~~^~
sequence.cpp:83:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |             assert(P1.size()-1<K && K<P2.size()-1);
      |                                     ~^~~~~~~~~~~~
sequence.cpp:85:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |             for(int i=0; i+1<P1.size() && i+x+1<P2.size(); i++)
      |                          ~~~^~~~~~~~~~
sequence.cpp:85:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |             for(int i=0; i+1<P1.size() && i+x+1<P2.size(); i++)
      |                                           ~~~~~^~~~~~~~~~
sequence.cpp:90:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |                     for(int j=i+1; j<P1.size(); j++) ansV.push(P1[j]);
      |                                    ~^~~~~~~~~~
sequence.cpp:90:59: error: 'class std::vector<int>' has no member named 'push'
   90 |                     for(int j=i+1; j<P1.size(); j++) ansV.push(P1[j]);
      |                                                           ^~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from sequence.cpp:1:
sequence.cpp:94:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   94 |         assert(ansV.size()==K+1);
      |                ~~~~~~~~~~~^~~~~