제출 #1343006

#제출 시각아이디문제언어결과실행 시간메모리
1343006nobasistakenGlobal Warming (CEOI18_glo)C++20
0 / 100
37 ms9684 KiB
#ifdef LOCAL
#include <C:\Users\onlin\Desktop\competitive_programming\codes\debug.hpp>
#else
    #define dbg(x) 
    #define dbgl(x) 
    #define dbgvec(v) 
    #define DBG_OF(i, v)
#endif
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define all(v) v.begin(),v.end()
bool testcases=0;
int dx[]={-1,1,-1,1,2,2,-2,-2};
int dy[]={-2,-2,+2,2,-1,1,-1,1};
const int MOD=1e9+7;
const int inf=1e12;
const int ranint=65729178;
const int mynum=21;
const int N=1e6;
const int siz=N+mynum;
const int tsiz=4*siz;
void solve(){
    int n;
    cin>>n;
    int x;
    cin>>x;
    vector<int> v(n+2);
    v[n+1]=0;
    v[0]=0;
    for(int i=1;i<=n;i++)cin>>v[i];
    vector<int> vc=v;
    for(int i=1;i<=n;i++){
        v[i]-=x;
    }
    array<int,2> pref[n+1],suf[n+2];
    vector<int> lis;
    reverse(vc.begin()+1,vc.begin()+n+1);
    for(int i=1;i<=n;i++){
        auto it=lower_bound(all(lis),v[i]);
        if(it==lis.end()){
            lis.push_back(v[i]);
        }
        else{
            lis[it-lis.begin()]=v[i];
        }
        pref[i]={lis.size(),lis.back()};
    }
    suf[n+1]={0,0};
    suf[0]=suf[n+1];
    lis.clear();
    for(int i=1;i<=n;i++){
        auto it=lower_bound(all(lis),vc[i]);
        if(it==lis.end()){
            lis.push_back(vc[i]);
        }
        else{
            lis[it-lis.begin()]=vc[i];
        }
        suf[i]={lis.size(),*lis.begin()};
    }
    reverse(suf+1,suf+n+1);
    int ans=suf[1][0];
    for(int i=1;i<=n;i++){
        auto [sval,snum]=suf[i+1];
        auto [pval,pnum]=pref[i];
        if(snum>pnum)ans=max(ans,pval+sval);
    }
    cout<<ans<<endl;
}
signed main() {
    iostream::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    if(testcases)cin>>t;
    while(t--){
        solve();
    }
}

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

glo.cpp: In function 'void solve()':
glo.cpp:48:26: warning: narrowing conversion of 'lis.std::vector<long long int>::size()' from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
   48 |         pref[i]={lis.size(),lis.back()};
      |                  ~~~~~~~~^~
glo.cpp:61:25: warning: narrowing conversion of 'lis.std::vector<long long int>::size()' from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
   61 |         suf[i]={lis.size(),*lis.begin()};
      |                 ~~~~~~~~^~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...