Submission #996499
Source Code Expand
#include <string> #include <vector> #include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <queue> #include <map> #include <set> #include <iostream> #include <sstream> #include <cstring> #include <numeric> using namespace std; typedef long long ll; typedef pair<int,int> pii; #define F0(i,n) for (int i = 0; i < n; i++) #define F1(i,n) for (int i = 1; i <= n; i++) #define CL(a,x) memset(x, a, sizeof(x)); #define SZ(x) ((int)x.size()) const double eps = 1e-10; const int inf = 1000000009; int i, j, k, m, n, l; int ans; string s; int dp[5001][5001]; int lessthan(int i, int j) { if (i == j) return 0; if (i == inf) return 1; if (j == inf) return 0; F0(l, k) if (s[i + l] != s[j + l]) return s[i + l] < s[j + l]; return 0; } int main() { //freopen("x.in", "r", stdin); cin >> m >> s; n = SZ(s); m++; k = (n + m - 1) / m; CL(-1, dp); dp[0][0] = inf; for (int j = 0; j < m; j++) for (int i = 0; i < n; i++) if (dp[i][j] != -1) { for (int ii = i + 1; ii <= n && ii <= i + k && n - ii <= k * (m - j); ii++) { int curr = (ii == i + k) ? i : inf; if (lessthan(curr, dp[i][j])) curr = dp[i][j]; if (dp[ii][j + 1] == -1) dp[ii][j + 1] = curr; else { if (lessthan(curr, dp[ii][j + 1])) dp[ii][j + 1] = curr; } } } cout << s.substr(dp[n][m], k) << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - Problem where Commas Separate Digits |
User | USA |
Language | C++14 (GCC 5.4.1) |
Score | 600 |
Code Size | 1395 Byte |
Status | RE |
Exec Time | 208 ms |
Memory | 98176 KB |
Judge Result
Set Name | Sample | Dataset1 | Dataset2 | Dataset3 | Dataset4 | Dataset5 | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | 100 / 100 | 200 / 200 | 200 / 200 | 0 / 400 | ||||||||||||||
Status |
|
|
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | subtask_02_ex1.txt, subtask_03_ex2.txt, subtask_03_ex3.txt |
Dataset1 | subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt |
Dataset2 | subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_ex1.txt |
Dataset3 | subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_ex1.txt, subtask_03_01.txt, subtask_03_02.txt, subtask_03_03.txt, subtask_03_04.txt, subtask_03_05.txt, subtask_03_06.txt, subtask_03_07.txt, subtask_03_08.txt, subtask_03_09.txt, subtask_03_10.txt, subtask_03_11.txt, subtask_03_12.txt, subtask_03_13.txt, subtask_03_14.txt, subtask_03_15.txt, subtask_03_ex2.txt, subtask_03_ex3.txt |
Dataset4 | subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_ex1.txt, subtask_03_01.txt, subtask_03_02.txt, subtask_03_03.txt, subtask_03_04.txt, subtask_03_05.txt, subtask_03_06.txt, subtask_03_07.txt, subtask_03_08.txt, subtask_03_09.txt, subtask_03_10.txt, subtask_03_11.txt, subtask_03_12.txt, subtask_03_13.txt, subtask_03_14.txt, subtask_03_15.txt, subtask_03_ex2.txt, subtask_03_ex3.txt, subtask_04_01.txt, subtask_04_02.txt, subtask_04_03.txt, subtask_04_04.txt, subtask_04_05.txt, subtask_04_06.txt, subtask_04_07.txt, subtask_04_08.txt, subtask_04_09.txt, subtask_04_10.txt, subtask_04_11.txt, subtask_04_12.txt, subtask_04_13.txt, subtask_04_14.txt, subtask_04_15.txt |
Dataset5 | subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_ex1.txt, subtask_03_01.txt, subtask_03_02.txt, subtask_03_03.txt, subtask_03_04.txt, subtask_03_05.txt, subtask_03_06.txt, subtask_03_07.txt, subtask_03_08.txt, subtask_03_09.txt, subtask_03_10.txt, subtask_03_11.txt, subtask_03_12.txt, subtask_03_13.txt, subtask_03_14.txt, subtask_03_15.txt, subtask_03_ex2.txt, subtask_03_ex3.txt, subtask_04_01.txt, subtask_04_02.txt, subtask_04_03.txt, subtask_04_04.txt, subtask_04_05.txt, subtask_04_06.txt, subtask_04_07.txt, subtask_04_08.txt, subtask_04_09.txt, subtask_04_10.txt, subtask_04_11.txt, subtask_04_12.txt, subtask_04_13.txt, subtask_04_14.txt, subtask_04_15.txt, subtask_05_01.txt, subtask_05_02.txt, subtask_05_03.txt, subtask_05_04.txt, subtask_05_05.txt, subtask_05_06.txt, subtask_05_07.txt, subtask_05_08.txt, subtask_05_09.txt, subtask_05_10.txt, subtask_05_11.txt, subtask_05_12.txt, subtask_05_13.txt, subtask_05_14.txt, subtask_05_15.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask_01_01.txt | AC | 95 ms | 97920 KB |
subtask_01_02.txt | AC | 94 ms | 97920 KB |
subtask_01_03.txt | AC | 94 ms | 97920 KB |
subtask_01_04.txt | AC | 94 ms | 97920 KB |
subtask_01_05.txt | AC | 94 ms | 97920 KB |
subtask_01_06.txt | AC | 95 ms | 97920 KB |
subtask_01_07.txt | AC | 94 ms | 97920 KB |
subtask_01_08.txt | AC | 94 ms | 97920 KB |
subtask_01_09.txt | AC | 94 ms | 97920 KB |
subtask_01_10.txt | AC | 95 ms | 97920 KB |
subtask_01_11.txt | AC | 94 ms | 97920 KB |
subtask_01_12.txt | AC | 94 ms | 97920 KB |
subtask_01_13.txt | AC | 94 ms | 97920 KB |
subtask_01_14.txt | AC | 94 ms | 97920 KB |
subtask_01_15.txt | AC | 94 ms | 97920 KB |
subtask_01_16.txt | AC | 94 ms | 97920 KB |
subtask_01_17.txt | AC | 94 ms | 97920 KB |
subtask_02_01.txt | AC | 94 ms | 97920 KB |
subtask_02_02.txt | AC | 95 ms | 97920 KB |
subtask_02_03.txt | AC | 94 ms | 97920 KB |
subtask_02_04.txt | AC | 94 ms | 97920 KB |
subtask_02_05.txt | AC | 95 ms | 97920 KB |
subtask_02_06.txt | AC | 94 ms | 97920 KB |
subtask_02_07.txt | AC | 94 ms | 97920 KB |
subtask_02_08.txt | AC | 94 ms | 97920 KB |
subtask_02_09.txt | AC | 94 ms | 97920 KB |
subtask_02_10.txt | AC | 95 ms | 97920 KB |
subtask_02_11.txt | AC | 94 ms | 97920 KB |
subtask_02_12.txt | AC | 94 ms | 97920 KB |
subtask_02_13.txt | AC | 95 ms | 97920 KB |
subtask_02_14.txt | AC | 94 ms | 97920 KB |
subtask_02_ex1.txt | AC | 94 ms | 97920 KB |
subtask_03_01.txt | AC | 95 ms | 97920 KB |
subtask_03_02.txt | AC | 94 ms | 97920 KB |
subtask_03_03.txt | AC | 95 ms | 97920 KB |
subtask_03_04.txt | AC | 94 ms | 97920 KB |
subtask_03_05.txt | AC | 94 ms | 97920 KB |
subtask_03_06.txt | AC | 94 ms | 97920 KB |
subtask_03_07.txt | AC | 94 ms | 97920 KB |
subtask_03_08.txt | AC | 94 ms | 97920 KB |
subtask_03_09.txt | AC | 94 ms | 97920 KB |
subtask_03_10.txt | AC | 94 ms | 97920 KB |
subtask_03_11.txt | AC | 94 ms | 97920 KB |
subtask_03_12.txt | AC | 94 ms | 97920 KB |
subtask_03_13.txt | AC | 95 ms | 97920 KB |
subtask_03_14.txt | AC | 94 ms | 97920 KB |
subtask_03_15.txt | AC | 94 ms | 97920 KB |
subtask_03_ex2.txt | AC | 94 ms | 97920 KB |
subtask_03_ex3.txt | AC | 94 ms | 97920 KB |
subtask_04_01.txt | AC | 135 ms | 97920 KB |
subtask_04_02.txt | AC | 103 ms | 97920 KB |
subtask_04_03.txt | AC | 135 ms | 97920 KB |
subtask_04_04.txt | AC | 115 ms | 97920 KB |
subtask_04_05.txt | AC | 108 ms | 97920 KB |
subtask_04_06.txt | AC | 105 ms | 97920 KB |
subtask_04_07.txt | AC | 102 ms | 97920 KB |
subtask_04_08.txt | AC | 95 ms | 97920 KB |
subtask_04_09.txt | AC | 94 ms | 97920 KB |
subtask_04_10.txt | AC | 105 ms | 97920 KB |
subtask_04_11.txt | AC | 105 ms | 97920 KB |
subtask_04_12.txt | AC | 105 ms | 97920 KB |
subtask_04_13.txt | AC | 94 ms | 97920 KB |
subtask_04_14.txt | AC | 95 ms | 97920 KB |
subtask_04_15.txt | AC | 98 ms | 97920 KB |
subtask_05_01.txt | RE | 206 ms | 98176 KB |
subtask_05_02.txt | RE | 207 ms | 98176 KB |
subtask_05_03.txt | RE | 206 ms | 98176 KB |
subtask_05_04.txt | RE | 207 ms | 98176 KB |
subtask_05_05.txt | RE | 207 ms | 98176 KB |
subtask_05_06.txt | RE | 207 ms | 98176 KB |
subtask_05_07.txt | RE | 206 ms | 98176 KB |
subtask_05_08.txt | RE | 206 ms | 98176 KB |
subtask_05_09.txt | RE | 207 ms | 98176 KB |
subtask_05_10.txt | RE | 208 ms | 98176 KB |
subtask_05_11.txt | RE | 208 ms | 98176 KB |
subtask_05_12.txt | RE | 206 ms | 98176 KB |
subtask_05_13.txt | RE | 205 ms | 98176 KB |
subtask_05_14.txt | RE | 207 ms | 98176 KB |
subtask_05_15.txt | RE | 204 ms | 98048 KB |