| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1312063 | eri16 | Mosaic (IOI24_mosaic) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll> mosaic(vector<int> X, vector<int> Y,vector<int> T, vector<int> B,vector<int> L, vector<int> R){
int arr[5005][5005];
int dp[5005][5005];
ll n = X.size();
for (int i=0; i<n; i++){arr[0][i]=X[i];}
for (int i=0; i<n; i++){arr[i][0]=Y[i];}
dp[0][0]=arr[0][0];
for (int i=1; i<n; i++){
dp[0][i]=dp[0][i-1]+arr[0][i];
dp[i][0]=dp[i-1][0]+arr[i][0];
}
for (int i=1; i<n; i++){
for (int j=1; j<n; j++){
arr[i][j]= 1 - (arr[i-1][j] | arr[i][j-1]);
dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]+arr[i][j];
}
}
ll q = T.size();
vector <ll> ans;
ll t,b,l,r;
for (int i=0; i<q; i++){
t=T[i];
b=B[i];
l=L[i];
r=R[i];
ll sm=dp[b][r];
if (l){sm-=dp[b][l-1];}
if (t){sm-=dp[t-1][r];}
if (l && t){sm+=dp[t-1][l-1];}
ans.push_back(sm);
}
return ans;
}
int main(){
vector <int> x = {1, 0, 1, 0};
vector <int> y = {1, 1, 0, 1};
vector <int> t = {0, 2};
vector <int> b = {3, 3};
vector <int> l = {0, 0};
vector <int> r = {3, 2};
vector <ll> ans = mosaic(x,y,t,b,l,r);
for (auto x : ans){cout<<x<<' ';}
}
