(cache)Submission #66133385 - AtCoder Beginner Contest 407

Contest Duration: 2025-05-24(Sat) 21:00 - 2025-05-24(Sat) 22:40 (local time) (100 minutes) Back to Home

Submission #66133385

Source Code Expand

Copy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        vector<long long> a(2 * n);
        for (int i = 0; i < 2 * n; i++) cin >> a[i];
        // dp[j]: j個の開き括弧がある状態の最大スコア
        vector<long long> dp(n + 1, -1);
        dp[0] = 0;
        for (int i = 0; i < 2 * n; i++) {
            vector<long long> ndp(n + 1, -1);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        vector<long long> a(2 * n);
        for (int i = 0; i < 2 * n; i++) cin >> a[i];

        // dp[j]: j個の開き括弧がある状態の最大スコア
        vector<long long> dp(n + 1, -1);
        dp[0] = 0;

        for (int i = 0; i < 2 * n; i++) {
            vector<long long> ndp(n + 1, -1);
            for (int j = 0; j <= n; j++) {
                if (dp[j] == -1) continue;
                // '('を追加
                if (j + 1 <= n) ndp[j + 1] = max(ndp[j + 1], dp[j] + a[i]);
                // ')'を追加
                if (j - 1 >= 0) ndp[j - 1] = max(ndp[j - 1], dp[j]);
            }
            dp = move(ndp);
        }

        cout << dp[0] << "\n";
    }

    return 0;
}

Submission Info

Submission Time	2025-05-24 22:37:02
Task	E - Most Valuable Parentheses
User	practicejoi
Language	C++ 20 (gcc 12.2)
Score	0
Code Size	962 Byte
Status	TLE
Exec Time	2208 ms
Memory	9552 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

0 / 450

Status

× 1

AC	× 8
TLE	× 10

Set Name	Test Cases
Sample	00-sample-01.txt
All	00-sample-01.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt

Case Name	Status	Exec Time	Memory
00-sample-01.txt	AC	1 ms	3480 KiB
01-01.txt	AC	1 ms	3464 KiB
01-02.txt	AC	1 ms	3424 KiB
01-03.txt	AC	1 ms	3488 KiB
01-04.txt	AC	1 ms	3324 KiB
01-05.txt	AC	175 ms	3484 KiB
01-06.txt	TLE	2207 ms	4756 KiB
01-07.txt	TLE	2208 ms	9552 KiB
01-08.txt	AC	89 ms	3692 KiB
01-09.txt	AC	227 ms	3468 KiB
01-10.txt	TLE	2208 ms	9408 KiB
01-11.txt	TLE	2207 ms	4812 KiB
01-12.txt	TLE	2208 ms	9388 KiB
01-13.txt	TLE	2207 ms	4792 KiB
01-14.txt	TLE	2208 ms	9312 KiB
01-15.txt	TLE	2207 ms	4760 KiB
01-16.txt	TLE	2208 ms	9388 KiB
01-17.txt	TLE	2207 ms	4768 KiB