Submission #43433083

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define MOD 998244353

int n, mi[6005], ma[6005];
long long da[6005][6005], db[6005][6005];
char x[6005];

int main() {
	scanf("%d%s", &n, x);
	mi[n * 2] = ma[n * 2] = 3002;
	for (int i = n * 2 - 1; i >= 0; i--)
		if (x[i] == '+') {
			mi[i] = mi[i + 1] + 1;
			ma[i] = ma[i + 1] + 1;
		} else if (x[i] == '-') {
			mi[i] = mi[i + 1] - 1;
			ma[i] = ma[i + 1] - 1;
		} else {
			mi[i] = mi[i + 1] - 1;
			ma[i] = ma[i + 1] + 1;
		}
	da[0][3002] = 1;
	mi[0] = ma[0] = 3002;
	for (int i = 0; i < n * 2; i++) {
		if (x[i] == '+') {
			mi[i + 1] = mi[i] + 1;
			ma[i + 1] = ma[i] + 1;
		} else if (x[i] == '-') {
			mi[i + 1] = mi[i] - 1;
			ma[i + 1] = ma[i] - 1;
		} else
			tie(mi[i + 1], ma[i + 1]) = make_pair(max(mi[i] - 1, -(ma[i + 1] - 3002) + 3002), min(ma[i] + 1, -(mi[i + 1] - 3002) + 3002));
		for (int j = mi[i]; j <= ma[i]; j++) {
			if (x[i] != '-' && j + 1 <= ma[i + 1]) {
				if (abs(j + 1 - 3002) > abs(j - 3002))
					db[i + 1][j + 1] = (db[i + 1][j + 1] + db[i][j] + MOD - da[i][j] * i % MOD) % MOD;
				else
					db[i + 1][j + 1] = (db[i + 1][j + 1] + db[i][j] + da[i][j] * i) % MOD;
				da[i + 1][j + 1] = (da[i + 1][j + 1] + da[i][j]) % MOD;
			}
			if (x[i] != '+' && j - 1 >= mi[i + 1]) {
				if (abs(j - 1 - 3002) > abs(j - 3002))
					db[i + 1][j - 1] = (db[i + 1][j - 1] + db[i][j] + MOD - da[i][j] * i % MOD) % MOD;
				else
					db[i + 1][j - 1] = (db[i + 1][j - 1] + db[i][j] + da[i][j] * i) % MOD;
				da[i + 1][j - 1] = (da[i + 1][j - 1] + da[i][j]) % MOD;
			}
		}
	}
	printf("%lld\n", db[n * 2][3002]);
}

Submission Info

Submission Time
Task D - 1D Coulomb
User nhho
Language C++ (GCC 9.2.1)
Score 600
Code Size 1638 Byte
Status AC
Exec Time 429 ms
Memory 330720 KiB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:12:7: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   12 |  scanf("%d%s", &n, x);
      |  ~~~~~^~~~~~~~~~~~~~~

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 2
AC × 42
Set Name Test Cases
Sample sample-01.txt, sample-02.txt
All in-01.txt, in-02.txt, in-03.txt, in-04.txt, in-05.txt, in-06.txt, in-07.txt, in-08.txt, in-09.txt, in-10.txt, in-11.txt, in-12.txt, in-13.txt, in-14.txt, in-15.txt, in-16.txt, in-17.txt, in-18.txt, in-19.txt, in-20.txt, in-21.txt, in-22.txt, in-23.txt, in-24.txt, in-25.txt, in-26.txt, in-27.txt, in-28.txt, in-29.txt, in-30.txt, in-31.txt, in-32.txt, in-33.txt, in-34.txt, in-35.txt, in-36.txt, in-37.txt, in-38.txt, in-39.txt, in-40.txt, sample-01.txt, sample-02.txt
Case Name Status Exec Time Memory
in-01.txt AC 8 ms 3820 KiB
in-02.txt AC 3 ms 3732 KiB
in-03.txt AC 9 ms 3836 KiB
in-04.txt AC 7 ms 3776 KiB
in-05.txt AC 2 ms 3732 KiB
in-06.txt AC 2 ms 3728 KiB
in-07.txt AC 3 ms 3636 KiB
in-08.txt AC 2 ms 3788 KiB
in-09.txt AC 429 ms 330720 KiB
in-10.txt AC 368 ms 303248 KiB
in-11.txt AC 368 ms 303672 KiB
in-12.txt AC 371 ms 306076 KiB
in-13.txt AC 216 ms 191132 KiB
in-14.txt AC 212 ms 190160 KiB
in-15.txt AC 216 ms 191968 KiB
in-16.txt AC 79 ms 78980 KiB
in-17.txt AC 83 ms 80268 KiB
in-18.txt AC 80 ms 79208 KiB
in-19.txt AC 340 ms 282464 KiB
in-20.txt AC 343 ms 284160 KiB
in-21.txt AC 342 ms 283944 KiB
in-22.txt AC 255 ms 210392 KiB
in-23.txt AC 310 ms 254168 KiB
in-24.txt AC 168 ms 152444 KiB
in-25.txt AC 174 ms 155304 KiB
in-26.txt AC 70 ms 67108 KiB
in-27.txt AC 60 ms 56808 KiB
in-28.txt AC 3 ms 4108 KiB
in-29.txt AC 4 ms 4952 KiB
in-30.txt AC 4 ms 4356 KiB
in-31.txt AC 4 ms 4288 KiB
in-32.txt AC 6 ms 4748 KiB
in-33.txt AC 5 ms 4840 KiB
in-34.txt AC 374 ms 301228 KiB
in-35.txt AC 346 ms 279764 KiB
in-36.txt AC 279 ms 226080 KiB
in-37.txt AC 361 ms 292596 KiB
in-38.txt AC 45 ms 47148 KiB
in-39.txt AC 38 ms 36280 KiB
in-40.txt AC 37 ms 38972 KiB
sample-01.txt AC 2 ms 3568 KiB
sample-02.txt AC 2 ms 3832 KiB