oj.uz

답안 #137455

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
137455 2019-07-27T18:51:25 Z nash Aliens (IOI16_aliens) C++14
0 / 100
 2 ms 376 KB 
#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;


long long int mnsquares = 1000000000;
vector<int> r, c;
int n;


//tehere is no point having overlapping squares

//at every point on the diagonal we have 2 choices - start a square here or  not

//if we do, try making the square any size between 1 and thew max

long long int dp(int k, int m, int covered, int idx, int got){
    if (k<0) return 100000000000;
    if (k==0 || idx==m){
            if (got==0) return 100000000000;
            for (int i=0;i<n;i++){
                if (got&(1<<i)==0){
                    return 100000000000000;
                }
            }
           // cout << k << ' ' << idx << ' ' << covered << endl;
            return covered;
            //we made it pat the end
    }

    long long int ans = dp(k, m, covered, idx+1, got);
    //i is size of photo
    for (int i=1;i<=m-idx;i++){
        int newgot=got;
        for (int a=0;a<n;a++){
            if (r[a]>=idx && r[a]<=idx+i && c[a]>=idx && c[a]<=idx+i){
                newgot|=(1<<a);
            }
        }
        ans=min(ans, dp(k-1, m, covered+((i+1)*(i+1)), idx+1, newgot));
    }
    return ans;

}


long long int take_photos(int N, int m, int k, vector<int> R, vector<int> C){
    n=N;
    r=R;
    c=C;
    return dp(k, m, 0, 0,0);

}
/*
int main()
{
    cout << take_photos(2,6,2,vector<int> ({1,4}),vector<int> ({4,1}));
    return 0;
}
*/

Compilation message

aliens.cpp: In function 'long long int dp(int, int, int, int, int)':
aliens.cpp:22:31: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
                 if (got&(1<<i)==0){
                         ~~~~~~^~~

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Correct answer: answer = 4
2 Correct 2 ms 376 KB Correct answer: answer = 4
3 Correct 2 ms 376 KB Correct answer: answer = 4
4 Incorrect 2 ms 376 KB Wrong answer: output = 4, expected = 12
5 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 256 KB Wrong answer: output = 4, expected = 1
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Correct answer: answer = 4
2 Correct 2 ms 376 KB Correct answer: answer = 4
3 Correct 2 ms 376 KB Correct answer: answer = 4
4 Incorrect 2 ms 376 KB Wrong answer: output = 4, expected = 12
5 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Correct answer: answer = 4
2 Correct 2 ms 376 KB Correct answer: answer = 4
3 Correct 2 ms 376 KB Correct answer: answer = 4
4 Incorrect 2 ms 376 KB Wrong answer: output = 4, expected = 12
5 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Correct answer: answer = 4
2 Correct 2 ms 376 KB Correct answer: answer = 4
3 Correct 2 ms 376 KB Correct answer: answer = 4
4 Incorrect 2 ms 376 KB Wrong answer: output = 4, expected = 12
5 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Correct answer: answer = 4
2 Correct 2 ms 376 KB Correct answer: answer = 4
3 Correct 2 ms 376 KB Correct answer: answer = 4
4 Incorrect 2 ms 376 KB Wrong answer: output = 4, expected = 12
5 Halted 0 ms 0 KB -