답안 #337777

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
337777	2020-12-21T14:57:19 Z	talant117408	최솟값 배열 (IZhO11_hyper)	C++17	100 / 100	380 ms	43116 KB

hyper

/*
    Code written by Talant I.D.
*/
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
 
//using namespace __gnu_pbds;
using namespace std;
 
//typedef tree <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
  
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;
  
inline bool isvowel(char ch){
    ch = tolower(ch);
    return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u');
}
  
inline bool isprime(int n){
    if(n < 2 || (n%2 == 0 && n != 2)) return false;
    for(int i = 3; i*i <= n; i++)
        if(n%i == 0) return false;
    return true;
}
 
class Union{
    private:
        vector <int> saizu, link;
    public:
        Union(int n){
            saizu.assign(n, 1); link.resize(n); 
            iota(all(link), 0);
        }
        int find(int n){
            if(link[n] == n) return n;
            return link[n] = find(link[n]);
        }
        int same(int a, int b){
            return find(a) == find(b);
        }
        void unite(int a, int b){
            if(same(a, b)) return;
             
            a = find(a); b = find(b);
            if(saizu[a] < saizu[b]) swap(a, b);
             
            saizu[a] += saizu[b];
            link[b] = a;
        }
        int getsize(int a){
            return saizu[find(a)];
        }
};
 
const int mod = 1e9+7;
 
ll mode(ll a){
    a %= mod;
    if(a < 0) a += mod;
    return a;
}
 
ll subt(ll a, ll b){
    return mode(mode(a)-mode(b));
}
 
ll add(ll a, ll b){
    return mode(mode(a)+mode(b));
}
 
ll mult(ll a, ll b){
    return mode(mode(a)*mode(b));
}
 
ll binpow(ll a, ll b){
    ll res = 1;
    while(b){
        if(b&1) res = mult(res, a);
        a = mult(a, a);
        b >>= 1;
    }
    return res;
}
 
int main(){
    do_not_disturb
    
    int n, m, i, j, k, l, g;
    cin >> n >> m;
    int dp[5][n][n][n][n];
    for(i = 0; i < n; i++)
        for(j = 0; j < n; j++)
            for(k = 0; k < n; k++)
                for(l = 0; l < n; l++){
                    cin >> dp[4][i][j][k][l];
                }
    
    
    for(i = 0; i < n; i++)
        for(j = 0; j < n; j++)
            for(k = 0; k < n; k++)
                for(l = 0; l < n; l++){
                    dp[3][i][j][k][l] = 2e9;
                    for(g = l; g < min(n, l+m); g++)
                        dp[3][i][j][k][l] = min(dp[3][i][j][k][l], dp[4][i][j][k][g]);
                }
    for(i = 0; i < n; i++)
        for(j = 0; j < n; j++)
            for(k = 0; k < n; k++)
                for(l = 0; l < n; l++){
                    dp[2][i][j][k][l] = 2e9;
                    for(g = k; g < min(n, k+m); g++)
                        dp[2][i][j][k][l] = min(dp[2][i][j][k][l], dp[3][i][j][g][l]);
                }
    for(i = 0; i < n; i++)
        for(j = 0; j < n; j++)
            for(k = 0; k < n; k++)
                for(l = 0; l < n; l++){
                    dp[1][i][j][k][l] = 2e9;
                    for(g = j; g < min(n, j+m); g++)
                        dp[1][i][j][k][l] = min(dp[1][i][j][k][l], dp[2][i][g][k][l]);
                }
    for(i = 0; i < n; i++)
        for(j = 0; j < n; j++)
            for(k = 0; k < n; k++)
                for(l = 0; l < n; l++){
                    dp[0][i][j][k][l] = 2e9;
                    for(g = i; g < min(n, i+m); g++)
                        dp[0][i][j][k][l] = min(dp[0][i][j][k][l], dp[1][g][j][k][l]);
                }
                
    for(i = 0; i+m-1 < n; i++)
        for(j = 0; j+m-1 < n; j++)
            for(k = 0; k+m-1 < n; k++)
                for(l = 0; l+m-1 < n; l++)
                    cout << dp[0][i][j][k][l] << ' ';
    
    return 0;
}

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	2 ms	620 KB	Output is correct
4	Correct	2 ms	620 KB	Output is correct
5	Correct	4 ms	620 KB	Output is correct
6	Correct	11 ms	1772 KB	Output is correct
7	Correct	10 ms	1644 KB	Output is correct
8	Correct	31 ms	3692 KB	Output is correct
9	Correct	42 ms	5352 KB	Output is correct
10	Correct	30 ms	3820 KB	Output is correct
11	Correct	76 ms	8940 KB	Output is correct
12	Correct	163 ms	17644 KB	Output is correct
13	Correct	185 ms	16620 KB	Output is correct
14	Correct	181 ms	22656 KB	Output is correct
15	Correct	281 ms	35564 KB	Output is correct
16	Correct	272 ms	23916 KB	Output is correct
17	Correct	248 ms	25324 KB	Output is correct
18	Correct	353 ms	43116 KB	Output is correct
19	Correct	312 ms	32236 KB	Output is correct
20	Correct	380 ms	30116 KB	Output is correct