Submission #211247

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
211247	2020-03-19 18:11:33	socho	Visiting Singapore (NOI20_visitingsingapore)	C++14	42 / 100	2090 ms	99324 KiB

VisitingSingapore

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"
using namespace std;
const int MXK = 1005;
const int MXN = 5005;
const int MXM = 5005;
int k, n, m, a, b;
int happy[MXK];
int events[MXN];
int want[MXM];
int dp[MXN][MXM];
int solve(int planday, int realday) {
  if (planday == m) return 0; // if we're at end of plan, no more to gain
  if (realday == n) {
    // no more days to do anything
    int re = (m - planday);
    int co = (re == 0) ? 0 : b * re + a;
    return co;
  }
  if (dp[planday][realday] != INT_MIN) return dp[planday][realday];
  int best = INT_MIN; // the best is nada
  // let's say we skip this day of plan
  // there are then m - planday - 1 remaining in plan so 
  for (int u=planday; u<m; u++) {
    // skip until day u of plan
    int skip = (u - planday + 1);
    int cost = ((skip == 0) ? 0 : b * skip + a);
    best = max(best, cost + solve(u+1, realday));
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 4 / 4
• Subtask 2: 6 / 6
• Subtask 3: 12 / 12
• Subtask 4: 7 / 7
• Subtask 5: 0 / 8
• Subtask 6: 13 / 13
• Subtask 7: 0 / 50