oj.uz

Submission #49697

# Submission time Handle Problem Language Result Execution time Memory
49697 2018-06-02T08:42:42 Z 강태규(#1275, imeimi2000) None (JOI16_worst_reporter2) C++11
15 / 100
 10 ms 4712 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

int n;
const int inf = 100;
int a[16], b[16], c[16], d[16];
int dp[16][1 << 16];

int pro_dp(int i, int st) {
    if (i == n) return 0;
    if (dp[i][st] != -1) return dp[i][st];
    dp[i][st] = inf;
    for (int j = 0; j < n; ++j) {
        if ((st >> j) & 1) continue;
        if (b[i] > d[j]) continue;
        dp[i][st] = min(dp[i][st], pro_dp(i + 1, st | (1 << j)) + (a[i] != c[j]));
    }
    return dp[i][st];
}

int main() {
    scanf("%d", &n);
    if (n > 16) return 0;
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", a + i, b + i);
    }
    
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", c + i, d + i);
    }
    
    for (int i = 0; i < (1 << 20); ++i) {
        dp[i >> 16][i & ((1 << 16) - 1)] = -1;
    }
    printf("%d\n", pro_dp(0, 0));
	return 0;
}

Compilation message

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
worst_reporter2.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", a + i, b + i);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
worst_reporter2.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", c + i, d + i);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4344 KB Output is correct
2 Correct 7 ms 4452 KB Output is correct
3 Correct 9 ms 4528 KB Output is correct
4 Correct 7 ms 4692 KB Output is correct
5 Correct 8 ms 4692 KB Output is correct
6 Correct 6 ms 4692 KB Output is correct
7 Correct 10 ms 4692 KB Output is correct
8 Correct 6 ms 4692 KB Output is correct
9 Correct 8 ms 4692 KB Output is correct
10 Correct 7 ms 4692 KB Output is correct
11 Correct 7 ms 4712 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4344 KB Output is correct
2 Correct 7 ms 4452 KB Output is correct
3 Correct 9 ms 4528 KB Output is correct
4 Correct 7 ms 4692 KB Output is correct
5 Correct 8 ms 4692 KB Output is correct
6 Correct 6 ms 4692 KB Output is correct
7 Correct 10 ms 4692 KB Output is correct
8 Correct 6 ms 4692 KB Output is correct
9 Correct 8 ms 4692 KB Output is correct
10 Correct 7 ms 4692 KB Output is correct
11 Correct 7 ms 4712 KB Output is correct
12 Incorrect 2 ms 4712 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4344 KB Output is correct
2 Correct 7 ms 4452 KB Output is correct
3 Correct 9 ms 4528 KB Output is correct
4 Correct 7 ms 4692 KB Output is correct
5 Correct 8 ms 4692 KB Output is correct
6 Correct 6 ms 4692 KB Output is correct
7 Correct 10 ms 4692 KB Output is correct
8 Correct 6 ms 4692 KB Output is correct
9 Correct 8 ms 4692 KB Output is correct
10 Correct 7 ms 4692 KB Output is correct
11 Correct 7 ms 4712 KB Output is correct
12 Incorrect 2 ms 4712 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4344 KB Output is correct
2 Correct 7 ms 4452 KB Output is correct
3 Correct 9 ms 4528 KB Output is correct
4 Correct 7 ms 4692 KB Output is correct
5 Correct 8 ms 4692 KB Output is correct
6 Correct 6 ms 4692 KB Output is correct
7 Correct 10 ms 4692 KB Output is correct
8 Correct 6 ms 4692 KB Output is correct
9 Correct 8 ms 4692 KB Output is correct
10 Correct 7 ms 4692 KB Output is correct
11 Correct 7 ms 4712 KB Output is correct
12 Incorrect 2 ms 4712 KB Output isn't correct
13 Halted 0 ms 0 KB -