Submission #115242

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
115242	2019-06-06 08:35:57	minhtung0404	Popeala (CEOI16_popeala)	C++17	100 / 100	1313 ms	7160 KiB

popeala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
const int N = 55;
const int inf = 2e9 + 7;
using namespace std;
int n, t, s, sc[20005], dp[N][20005], cur[20005];
string a[N];
deque <int> mq[N];
void Insert(int id, int i, int j){
    while (mq[id].size() && dp[i][mq[id].back()]  >= dp[i][j]) mq[id].pop_back();
    mq[id].push_back(j);
}
void Erase(int id, int i, int j){
    if (mq[id].size() && mq[id].front() == j) mq[id].pop_front();
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> t >> s;
    for (int i = 1; i <= t; i++) cin >> sc[i], sc[i] += sc[i-1];
    for (int i = 1; i <= n; i++) cin >> a[i], a[i] = '.' + a[i];
    for (int i = 0; i < N; i++) for (int j = 0; j < 20005; j++) dp[i][j] = inf;
    dp[0][0] = 0;
    for (int sub = 1; sub <= s; sub++){
        for (int j = 0; j <= n; j++) mq[j].clear();
        Insert(n, sub-1, 0); cur[0] = n;
        for (int test = 1; test <= t; test++){
            for (int peo = 1; peo <= n; peo++){
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 74 / 74