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
31
32
33
34
35

#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e5+7, mod=1e9+7;

int n,r;
int a[N];

void solve(){
    cin>>n>>r;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+1+n);
    int ans=0,lft=0;
    for(int i=n;i>0;i--){
        ans+=(a[i]/2)*2;
        r-=a[i]/2;
        lft+=a[i]%2;
    }
    ans+=min(lft,r);
    ans-=max(0,(lft-r));
    cout<<ans<<endl;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}

 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
31
32
33

#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
#define int long long
const int N=5e5+7, mod=1e9+7;

int n,x;
int ans,a[N],sum;

void solve(){
    ans=sum=0;
    cin>>n>>x;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
        ans=max(ans,a[i]);
    }
    if(ans*x>sum)cout<<ans<<endl;
    else cout<<(int)ceil(1.0*sum/x)<<endl;

}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}

 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e5+7, mod=1e9+7;

bool check(char a,char b,char c){
    int res=(a=='A')+(b=='A')+(c=='A');
    return res>=2;
}

int n;
char mp[3][N];
int dp[5][N];

void solve(){
    cin>>n;
    for(int i=0;i<2;i++)
        for(int j=1;j<=n;j++)cin>>mp[i][j];
    memset(dp,0,sizeof(dp));
    dp[0][1]=0;
    for(int i=1;i<=n;i++){
        if(i%3==1){
            dp[0][i+3]=max(dp[0][i+3],dp[0][i]+check(mp[0][i],mp[0][i+1],mp[0][i+2])+check(mp[1][i],mp[1][i+1],mp[1][i+2]));
            dp[0][i+1]=max(dp[0][i+1],dp[0][i]+check(mp[0][i],mp[1][i],mp[0][i+1]));
            dp[1][i+1]=max(dp[1][i+1],dp[0][i]+check(mp[1][i],mp[0][i],mp[1][i+1]));
        }
        else if(i%3==2){
            if(i<=n-3){
                dp[0][i+3]=max(dp[0][i+3],dp[0][i]+check(mp[0][i+1],mp[0][i+2],mp[0][i+3])+check(mp[1][i],mp[1][i+1],mp[1][i+2]));
                dp[1][i+3]=max(dp[1][i+3],dp[1][i]+check(mp[0][i],mp[0][i+1],mp[0][i+2])+check(mp[1][i+1],mp[1][i+2],mp[1][i+3]));
            }
            dp[0][i+2]=max(dp[0][i+2],dp[0][i]+check(mp[1][i],mp[1][i+1],mp[0][i+1]));
            dp[0][i+2]=max(dp[0][i+2],dp[1][i]+check(mp[0][i+1],mp[0][i],mp[1][i+1]));
        }
    }
    cout<<dp[0][n+1]<<endl;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}

 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e5+7, mod=1e9+7;

int n;

bool query(int x,int y){
    cout<<"? "<<x<<" "<<y<<endl;
    int fx,fy;
    cin>>fx;
    cout<<"? "<<y<<" "<<x<<endl;
    cin>>fy;
    return fx!=fy;
}

void solve(){
    cin>>n;
    int pos=-1;
    for(int i=1;i<n;i+=2){
        bool flag=query(i,i+1);
        if(flag){
            pos=i;
            break;
        }
    }
    if(pos==-1)cout<<"! "<<n<<endl;
    else if(query(pos,pos>1?pos-1:pos+2))
        cout<<"! "<<pos<<endl;
    else cout<<"! "<<pos+1<<endl;
}

int main(){
    // ios::sync_with_stdio(0);
    // cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}