oj.uz

Submission #1118137

# Submission time Handle Problem Language Result Execution time Memory
1118137 2024-11-25T03:31:56 Z overwatch9 Nizin (COCI16_nizin) C++17
60 / 100
 135 ms 65536 KB 
#include <bits/stdc++.h>
using namespace std;
int n;
vector <int> nums;
vector <vector <int>> dp;
int solve(int l, int r) {
    if (l >= r)
        return 0;
    if (dp[l][r] != -1)
        return dp[l][r];
    int ans = 1e9;
    if (nums[l] == nums[r])
        ans = solve(l+1, r-1);
    else {
        nums[l+1] += nums[l];
        ans = min(ans, solve(l+1, r) + 1);
        nums[l+1] -= nums[l];
        nums[r-1] += nums[r];
        ans = min(ans, solve(l, r-1) + 1);
        nums[r-1] -= nums[r];
    }
    dp[l][r] = ans;
    return ans;
}
int main() {
    cin >> n;
    nums.resize(n);
    for (int i = 0; i < n; i++)
        cin >> nums[i];
    dp = vector <vector <int>> (n, vector <int> (n, -1));
    cout << solve(0, n-1) << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1360 KB Output is correct
2 Correct 7 ms 2384 KB Output is correct
3 Correct 9 ms 3664 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3664 KB Output is correct
2 Correct 12 ms 4444 KB Output is correct
3 Correct 10 ms 4444 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 69 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 119 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 135 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 135 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -