oj.uz

답안 #834870

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
834870 2023-08-22T21:28:16 Z Ozy Lamps (JOI19_lamps) C++17
0 / 100
 7 ms 6640 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define pll pair<lli,lli>

#define MAX 2000
#define INF (1ll<<60)

string st,fin;
lli n,a,b;
lli cambios[MAX+2],arr[MAX+2],dp[MAX+2],xors[MAX+2];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> st >> fin;

    rep(i,2,n) { //primero hare el de los cambios
        cambios[i] = cambios[i-1];
        if(fin[i-2] != fin[i-1]) cambios[i]++; 
    }

    rep(i,1,n) { //ahora el de los xors
        arr[i] = abs(st[i-1] - fin[i-1]);
        xors[i] = xors[i-1];
        if(arr[i] == 1 && arr[i-1] == 0) xors[i]++; 
    }

    rep(i,1,n) {
        dp[i] = INF;
        repa(j,i,1) {

            a = xors[i] - xors[j];
            if (arr[j]) a++;

            b = cambios[i] - cambios[j];
            b = 1 + (b+1)/2; 

            dp[i] = min(dp[i], dp[j-1] + min(a,b));
        }
        //debug(dp[1]);
    }

    cout << dp[n];

    return 0;  
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Incorrect 1 ms 320 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Incorrect 1 ms 320 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Runtime error 7 ms 6640 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Incorrect 1 ms 320 KB Output isn't correct
14 Halted 0 ms 0 KB -