답안 #262174

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
262174 2020-08-12T12:47:37 Z leaked Mobitel (COCI19_mobitel) C++14
26 / 130
46 ms 10112 KB
//C.cpp
#include<bits/stdc++.h>
using namespace std;
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
//
//    #pragma GCC optimize("unroll-loops")
//    #pragma GCC optimize("Ofast")
//    #pragma GCC optimize("-O3")
//    #pragma GCC optimize("no-stack-protector")
//    #pragma GCC optimize("fast-math")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//#define LOCAL
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifndef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
	*this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define fi first
#define f first
#define se second
#define s second
#define vi_a vector<int>a;
#define p_b push_back
////////////////////////////////???????????????CHECK THIS OUT???????????????//////////////////////////////
#define ll long long
typedef unsigned long long ull;
////////////////////////////////???????????????CHECK THIS OUT???????????????//////////////////////////////
#define ld long double
#define pll pair<ll,ll>
#define pii pair<int,int>
#define m_p make_pair
#define fast_io cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);
#define all(x) x.begin(),x.end()
#define getfiles    ifstream cin("input.txt");ofstream cout("output.txt");
#define pw(x) (1ll << x)
#define sz(x) (int)x.size()
#define endl "\n"
#define rall(x) x.rbegin(),x.rend()
#define len(a) (ll)a.size()
#define rep(x,l,r) for(ll x=l;x<r;x++)

//using namespace __gnu_pbds;
ld eps = (ld)1 / 1e6;
const ld pi=3.14159265359;
ll inf = 1e18,mod1=1e9+7;
ll sqr(ll a) { return a * a; }
ll qb(ll a) { return a * a * a; }
template<typename T> bool umax(T& a, T b) {return a<b?a=b,1:0;}
template<typename T> bool umin(T& a, T b) {return b<a?a=b,1:0;}
bool is_prime(ll val){for(ll i=2;i<=sqrt(val);i++)if(val%i==0)return 0; return 1;}
ll gcd(ll a, ll b) { return !a ? b : gcd(b % a, a); }
ll binpow(ll a, ll b, ll mod) { return b ? (b % 2 ? (a * (sqr(binpow(a, b / 2, mod)) % mod)) % mod : sqr(binpow(a, b / 2, mod)) % mod) : 1; }ll binmult(ll a, ll b, ll mod) { return b ? (b % 2 ? (2 * binmult(a, b / 2, mod) + a) % mod : (2 * binmult(a, b / 2, mod)) % mod) : 0; }
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
const ll R=1e4;
const ll tx[4]={0,0,-1,1};
const ll ty[4]={-1,1,0,0};
const char rev_to[4]={'E','W','N','S'};
const int M=999999937;
const int N=1e6+2;
//const int MOD=1e9+7;
const int ppp=73;
const int Y=1e3+1;
const int X=1e6+1;
typedef pair<long long,int> pli;
//typedef tree<pli,null_type,less<pli>,rb_tree_tag,tree_order_statistics_node_update> o_st;
auto rnd=bind(uniform_int_distribution<ll>(1,125),mt19937(time(0)));
void bad(){
    cout<<"-1";
    exit(0);
}
int f[2][304][1300];
int a[304][304];
int pos[N],inv[1300];
void add(int &a,int b){
    a=(a+b)%mod1;
}
int p(int a,int b){
    return (1ll*a*b)%mod1;
}

signed main()
{
    fast_io;
//    freopen("in.txt","r",stdin);
    int n,m,k;
    cin>>n>>m>>k;
    int last=k+1;
//    k=N;
    int ps=0;
    for(int i=1;i<=k;i++){
        int cur=last;
        while(1ll*cur*i>=k) cur--;
        cur++;
        if(cur!=last) ps++;
        pos[i]=ps;
        inv[ps]=i;
        last=cur;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++) cin>>a[i][j],umin(a[i][j],k);
    }
    int ans=0;
    f[0][0][pos[1]]=1;
    for(int i=0;i<n;i++){
        int o=i%2,y=o^1;
        for(int j=0;j<m;j++){
            for(int z=1;z<=ps;z++){
                ll nw=min((ll)k,1ll*a[i][j]*inv[z]);
                if(i+1<n) add(f[y][j][pos[nw]],f[o][j][z]);
                if(j+1<m) add(f[o][j+1][pos[nw]],f[o][j][z]);
                if(i==n-1 && j==m-1 && nw==k) add(ans,f[o][j][z]);
                f[o][j][z]=0;
            }
        }
    }
    cout<<ans;
    return 0;
}
/*


*/
# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 3200 KB Output is correct
2 Correct 46 ms 3200 KB Output is correct
3 Runtime error 13 ms 8704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 13 ms 9728 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 14 ms 9728 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 14 ms 9856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 12 ms 8832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 15 ms 9984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 19 ms 10112 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 19 ms 10112 KB Execution killed with signal 11 (could be triggered by violating memory limits)