Submission #113658

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
113658	2019-05-27 13:22:12	Akashi	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	216 ms	512 KiB

sculpture

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;
int n, a, b;
long long x[2005];
int d[2005];
bool dp[105][105];
inline bool check(long long mask){
    if(n <= 100){
        memset(dp, 0, sizeof(dp));
        ///can we divide first i elements into j groups
        dp[0][0] = 1;
        for(int i = 1; i <= n ; ++i){
            for(int j = 0; j < i ; ++j){
                for(int k = 1; k <= b ; ++k){
                    if(dp[j][k - 1] && (x[i] - x[j]) - ((x[i] - x[j]) & mask) == 0)
                        dp[i][k] = 1;
                }
            }
        }
        for(int k = a; k <= b ; ++k)
            if(dp[n][k]) return 1;
    }
    else{
        memset(d, 0x3f, sizeof(d));
        d[0] = 0;
        for(int i = 1; i <= n ; ++i){
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:49:33: warning: integer overflow in expression [-Woverflow]
     long long Sol = (1LL << 63) - 1;
                     ~~~~~~~~~~~~^~~
sculpture.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &a, &b);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:47:54: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n ; ++i) scanf("%lld", &x[i]), x[i] += x[i - 1];
                                  ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 21 / 21
• Subtask 4: 25 / 25
• Subtask 5: 29 / 29