oj.uz

Submission #93104

# Submission time Handle Problem Language Result Execution time Memory
93104 2019-01-06T13:27:41 Z Ahmad_Elsisy Kas (COCI17_kas) C++14
70 / 100
 333 ms 198136 KB 
#include <bits/stdc++.h>
#define pb push_back
#define all(v) (v).begin() , (v).end()
#define popcnt(x) __builtin_popcount(x)
#define inf 0x3f3f3f3f
#define watch(x) cout << (#x) << " is " << (x) << endl

using namespace std;
typedef long long  ll;
const int N = 505 , M = 1e5 + 4;
int n , memo[N][M];
vector<int> a;

int solve(int indx , int s){
    if(indx == n){
        return (!s ? 0 : -inf);
    }

    int &ret = memo[indx][s];
    if(~ret)
        return ret;

    ret = -inf;
    ret = max(ret , 1 + solve(indx + 1 , s + a[indx]));
    ret = max(ret , 1 + solve(indx + 1 , abs(s - a[indx])));
    ret = max(ret , solve(indx + 1 , s));
    return ret;
}

int v , sum = 0;
void path(int indx , int s){
    if(indx == n){
        return;
    }

    int mx = solve(indx , s);
    if(1 + solve(indx + 1 , s + a[indx]) == mx){
        sum += a[indx];
        path(indx + 1 , s + a[indx]);
    }
    else if(1 + solve(indx + 1 , abs(s - a[indx])) == mx){
        sum += a[indx];
        path(indx + 1 , abs(s - a[indx]));
    }
    else{
        path(indx + 1 , s);
    }
}
int main() {
    ios::sync_with_stdio() , cin.tie(0) , cin.tie(0);
    int tot = 0;
    cin >> n;
    a.resize(n);
    for(int &x : a)
        cin >> x , tot += x;
    memset(memo , -1 , sizeof memo);
    v = solve(0 , 0);

    path(0 , 0);
    sum /= 2;

    cout << sum + (tot - 2 * sum) << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 198008 KB Output is correct
2 Correct 154 ms 198008 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 198008 KB Output is correct
2 Correct 154 ms 198008 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 198008 KB Output is correct
2 Correct 155 ms 197980 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 159 ms 197976 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 198040 KB Output is correct
2 Correct 157 ms 197960 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 197984 KB Output is correct
2 Correct 157 ms 198008 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 197976 KB Output is correct
2 Correct 155 ms 198020 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 197972 KB Output is correct
2 Correct 154 ms 198008 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 198112 KB Output is correct
2 Incorrect 251 ms 198008 KB Output isn't correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 333 ms 198136 KB Output isn't correct
2 Halted 0 ms 0 KB -