编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#107940 #1044. mm和tt吃糖果 Accepted 100 38 ms 500 K C++ 17 / 1.5 K 7k1danWhen 2024-07-05 12:35:11
显示原始代码
#include <bits/stdc++.h>
using namespace std;

#define ONLINE
#ifndef ONLINE
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define debug(...) ;
#endif

using LL = long long;
using PII = pair<int, int>;

#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()

template <typename T>
inline T READ() {
    T x = 0;
    bool f = 0;
    char c = getchar();
    while (!isdigit(c)) f |= (c == '-'), c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    return f ? -x : x;
}
inline int read() { return READ<int>(); }
inline LL readLL() { return READ<LL>(); }
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

#define N 30
int a[N][N];
LL f[N * 2][N][N];

int main() {
    int n = read();
    for (int T = read(); T--;) {
        int x = read(), y = read();
        a[x][y] = read();
    }
    f[0][1][1] = a[1][1];
    for (int i = 1; i <= n * 2 - 2; i++) {
        debug("i=%d\n", i);
        for (int j = 1; j <= n; j++) {
            int y1 = 2 + i - j;
            debug("\tj=%d y1=%d\n", j, y1);
            if (y1 < 1 || y1 > n)
                continue;
            for (int k = 1; k <= n; k++) {
                int y2 = 2 + i - k;
                if (y2 < 1 || y2 > n)
                    continue;
                LL add = a[j][y1];
                if (j != k)
                    add += a[k][y2];
                f[i][j][k] = max({ f[i][j][k], f[i - 1][j - 1][k - 1] + add, f[i - 1][j - 1][k] + add,
                                   f[i - 1][j][k - 1] + add, f[i - 1][j][k] + add });
                debug("f[%d][%d][%d]=%lld\n", i, j, k, f[i][j][k]);
            }
        }
    }
    cout << f[n * 2 - 2][n][n];
    return 0;
}

/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */
子任务 #1
Accepted
得分:100
测试点 #1
Accepted
得分:100
用时:3 ms
内存:248 KiB

输入文件(dat1.in

1 0

答案文件(dat1.out

0

用户输出

0

系统信息

Exited with return code 0
测试点 #2
Accepted
得分:100
用时:4 ms
内存:400 KiB

输入文件(dat2.in

8 8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14

答案文件(dat2.out

67

用户输出

67

系统信息

Exited with return code 0
测试点 #3
Accepted
得分:100
用时:4 ms
内存:384 KiB

输入文件(dat3.in

7 8
1 6 1114
7 6 3302
3 5 8809
5 7 6549
4 1 9234
2 4 2576
6 7 7404
1 3 3428

答案文件(dat3.out

41302

用户输出

41302

系统信息

Exited with return code 0
测试点 #4
Accepted
得分:100
用时:3 ms
内存:320 KiB

输入文件(dat4.in

1 1
1 1 2002

答案文件(dat4.out

2002

用户输出

2002

系统信息

Exited with return code 0
测试点 #5
Accepted
得分:100
用时:4 ms
内存:500 KiB

输入文件(dat5.in

15 13
9 12 5311
14 3 5481
6 7 103
10 15 1588
8 6 4303
7 3 4366
9 14 8753
1 7 3531
7 4 7946
10 11 948
<30 bytes omitted>

答案文件(dat5.out

56687

用户输出

56687

系统信息

Exited with return code 0
测试点 #6
Accepted
得分:100
用时:4 ms
内存:384 KiB

输入文件(dat6.in

10 46
6 8 2667
7 3 8930
3 2 5009
4 2 6798
3 10 4997
2 9 7426
10 1 6357
1 9 7255
2 7 5686
5 9 6333
10
<329 bytes omitted>

答案文件(dat6.out

154577

用户输出

154577

系统信息

Exited with return code 0
测试点 #7
Accepted
得分:100
用时:4 ms
内存:452 KiB

输入文件(dat7.in

18 304
11 14 1093
12 3 1501
15 11 5475
8 17 8966
17 4 3364
3 17 7874
14 4 9899
2 12 3693
7 16 9702
7
<2914 bytes omitted>

答案文件(dat7.out

446391

用户输出

446391

系统信息

Exited with return code 0
测试点 #8
Accepted
得分:100
用时:4 ms
内存:392 KiB

输入文件(dat8.in

13 27
13 3 4802
12 2 4950
2 2 381
4 1 4176
8 2 4058
11 8 7287
6 12 7503
5 7 7417
7 8 1488
2 6 8930
4
<159 bytes omitted>

答案文件(dat8.out

98678

用户输出

98678

系统信息

Exited with return code 0
测试点 #9
Accepted
得分:100
用时:4 ms
内存:392 KiB

输入文件(dat9.in

8 22
4 6 8511
8 6 4752
6 7 5287
7 5 9386
8 5 4752
5 5 347
8 7 5107
4 3 4788
2 4 9280
8 8 2424
2 3 11
<101 bytes omitted>

答案文件(dat9.out

83839

用户输出

83839

系统信息

Exited with return code 0
测试点 #10
Accepted
得分:100
用时:4 ms
内存:324 KiB

输入文件(dat10.in

3 0

答案文件(dat10.out

0

用户输出

0

系统信息

Exited with return code 0