제출 #1196388

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1196388		fluke	Kas (COCI17_kas)	C++20	70 / 100	201 ms	216244 KiB

kas

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define ordered_set <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define ordered_multiset <int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>

#define ll long long 
#define f first 
#define s second 
#define emb emplace_back 
#define emf emplace_front 
#define em emplace 
#define all(x) x.begin(),x.end()
#define DB cout<<"\n";system("pause");
#define sp <<" "<<
#define inf (int)(1e9)
#define INF (ll)(1e18)
#define mod (int)(1e9 + 7)
#define maxn 55

int n,max_sum , sum;
int vec[maxn];
void way(int ind , int sum1 , int sum2){
    if(ind == n+1){
        if(sum1 == sum2){
            max_sum = max(max_sum , sum1);
        }
        return ;
    }

    way(ind + 1 , sum1 + vec[ind] , sum2);
    way(ind + 1 , sum1  , sum2 + vec[ind]);
    way(ind + 1 , sum1  , sum2);
}


int mem[maxn][1001][1001];
bool solve2(int pos,int sum1 , int sum2){
    if(sum1 == 0 && sum2 == 0)return true;
    if(pos >= n + 1)return false;
    else if(sum1 < 0 || sum2 < 0)return false;
    else if(mem[pos][sum1][sum2] != -1)return mem[pos][sum1][sum2];

    
    return mem[pos][sum1][sum2] = solve2(pos + 1 , sum1 - vec[pos] , sum2) ||
                                  solve2(pos + 1 , sum1 , sum2 - vec[pos]) ||
                                  solve2(pos + 1 , sum1 , sum2);
}



int main(){
ios::sync_with_stdio(false);cin.tie(0);
    cin>>n;
    
    for(int i=1;i<=n;i++){
        cin>>vec[i];
        sum += vec[i];
    }

    if(n <= 13){
        way(1,0,0);
        cout<<max_sum + (sum - max_sum * 2);
        return 0;
    }
    else {
        memset(mem,-1,sizeof(mem));
        // cout<<solve2(1,13,13);
        for(int i=sum / 2; i >= 0 ; i--){
            if(solve2(1,i,i)){
                cout<< i + (sum - 2*i);
                return 0;
            }
        }
    }







}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10