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
AC × 3
AC × 17
AC × 32
AC × 49
AC × 64
AC × 64
RE × 15
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