제출 #785511

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
785511		andecaandeci	Global Warming (CEOI18_glo)	C++17	75 / 100	2069 ms	6188 KiB

glo

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int n, x; cin >> n >> x;
  if(x==0) {
    vector<int> a(n); for(int &p : a) cin >> p;
  vector<int> dp; int ans=1;
    for(int p : a) {
      auto it=lower_bound(dp.begin(), dp.end(), p);
      if(it==dp.end()) dp.push_back(p);
      else *it=p;
    }
    ans=dp.size();
    cout << ans << '\n';
  } else if(x<=5 && n<=50000) {
    vector<int> a, b;
      while(n--) {
      int p; cin >> p;
      vector<int> tempaa=a;
      auto it=lower_bound(tempaa.begin(), tempaa.end(), p);
      if(it==tempaa.end()) tempaa.push_back(p);
      else *it=p;
      vector<int> tempba=b;
      it=lower_bound(tempba.begin(), tempba.end(), p);
      if(it==tempba.end()) tempba.push_back(p);
      else *it=p;
      if(tempaa.size()>tempba.size()) a=tempaa;
      else a=tempba; p-=x;
      it=lower_bound(b.begin(), b.end(), p); 
      if(it==b.end()) b.push_back(p);
      else *it=p;
    }
    int ans=max((int)a.size(), (int)b.size());
    cout << ans << '\n';
    } else if(x==(int)1e9) {
      int ans=1;
      vector<int> a(n), b, pre(n);
      for(int &p : a) cin >> p;
      b=a; reverse(b.begin(), b.end());
      vector<int> dp;
      for(int i=0; i<n; i++) {
        int l=0, r=dp.size()-1, idx=-1;
        while(l<=r) {
          int mid=l+r>>1;
          if(b[i]>=dp[mid]) r=mid-1, idx=mid;
          else l=mid+1;
      }
      if(idx==-1) dp.push_back(b[i]);
      else dp[idx]=b[i];
      pre[i]=dp.size();
    }
    dp.clear();
    for(int i=0; i<n-1; i++) {
      auto it=lower_bound(dp.begin(), dp.end(), a[i]);
      if(it==dp.end()) dp.push_back(a[i]);
      else *it=a[i];
      ans=max(ans, (int)dp.size()+pre[n-i-2]);
    }
    cout << ans << '\n';
    } else {
      vector<int> a(n); for(int &p : a) cin >> p;
      vector<int> dp; int ans=1;
      for(int i=0; i<n; i++) {
          dp.clear();
          vector<int> temp=a;
          for(int k=i; k<n; k++) temp[k]+=x;
          for(int p : temp) {
            auto it=lower_bound(dp.begin(), dp.end(), p);
            if(it==dp.end()) dp.push_back(p);
            else *it=p;    
            }
          ans=max(ans, (int)dp.size());
          
      }
      cout << ans << '\n';
    }
    return 0;
}   

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

glo.cpp: In function 'int main()':
glo.cpp:30:7: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
   30 |       else a=tempba; p-=x;
      |       ^~~~
glo.cpp:30:22: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
   30 |       else a=tempba; p-=x;
      |                      ^
glo.cpp:46:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |           int mid=l+r>>1;
      |                   ~^~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 0 / 25