Submission #935152

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
935152	2024-02-28 18:02:05	kim	Chorus (JOI23_chorus)	C++17	61 / 100	7015 ms	15192 KiB

chorus

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
#define f first
#define s second
const ll inf=1e18;
int a[1000005],b[1000005],pos[1000005],pos2[1000005];
ll dp[2][1000005],qs[1000005];
ll f(int L,int R){
    int x=pos2[L];
    if(x>R) return 0;
    return qs[R]-qs[x-1]-L*(R-x+1);
}
void play(int l,int r,int optl,int optr,int z){
    if(l>r) return;
    int mid=l+r>>1;
    pair<ll,int> best(inf,0);
    for(int i=optl;i<=min(mid,optr);++i){
        best=min(best,{dp[!z][i-1]+f(i,mid),i});
    }
    dp[z][mid]=best.f;
    play(l,mid-1,optl,best.s,z);
    play(mid+1,r,best.s,optr,z);
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

chorus.cpp: In function 'void play(int, int, int, int, int)':
chorus.cpp:21:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |     int mid=l+r>>1;
      |             ~^~
chorus.cpp: In function 'int main()':
chorus.cpp:36:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int i=0,ia=0,ib=0;i<s.length();++i){
      |                           ~^~~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 24 / 24
• Subtask 3: 21 / 21
• Subtask 4: 0 / 26
• Subtask 5: 0 / 13