oj.uz

답안 #120556

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
120556 2019-06-24T23:12:47 Z _Samir Automobil (COCI17_automobil) C++17
55 / 100
 59 ms 8312 KB 
/*
   we will use dp , our state will be left most house i visited , the right most house i visited and
   the time till now , each time will try to visit new house from the left or the right
*/
#include<queue>
#include<map>
#include <string>
#include<bits/stdc++.h>
#define pi 3.141592654
#define forr(i,a,b) for(int i=a;i<=b;i++)
#define F first
#define S second
#define input ios_base::sync_with_stdio(0);cin.tie(0);
//#define x real()
//#define y imag()
using namespace std;
typedef pair<double,double>pdd;
typedef long long  ll;
typedef pair<ll, ll>pii;
//typedef complex<double> point;
//template<typename T>T gcd(T x, T y) { if(y == 0)return x; else return gcd(y, x%y); }
//typedef bitset<30> mask;
//int x[8]={1,0,0,-1,-1,-1,1,1};
//int y[8]={0,1,-1,0,-1,1,-1,1};
//#define var(x) ((x)<<1)
//#define nvar(x) ((x)^1)
const int N=100000,M=100000;

ll n,m,k;
map<ll,ll>r,c;
ll sum,mod=1e9+7,R[1000004],pls;
 main()
{

//cout<<Pow((ll)1000000,(ll)110);
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
//    char input[15];
//    scanf("%s", &input);  array of char
//  gets(c+1);  array of char
//printf("%s, ",name[k[i]].c_str());  printf of string
//priority_queue<ll,vector<ll>,greater<ll>>y;
input;

cin>>n>>m>>k;
for(ll i=1;i<=n;i++)
{
   R[i]=(i-1)*m*m+m*(m+1)/2;
   R[i]%=mod;
}


char t;
ll x,y;
forr(i,1,k)
{
    cin>>t>>x>>y;
    if(t=='S')
    {
        if(c.count(x)==0)c[x]=1;
        c[x]*=y;
        c[x]%=mod;
    }
    else
    {
        if(r.count(x)==0)r[x]=1;
        r[x]*=y;
        r[x]%=mod;
    }
}

for(auto b:c)
{
    ll g =b.F*n+n*(n-1)/2*m;
    g%=mod;
    for(auto a:r)
    {
        ll num=(a.F-1)*m+b.F;
        R[a.F]-=num;
        R[a.F]+=num*b.S;
        R[a.F]%=mod;
        g-=num;
        g%=mod;
    }
    pls+=((b.S-1)*g)%mod;
    pls%=mod;
}

for(auto a:r)R[a.F]=(R[a.F]*a.S)%mod;

forr(i,1,n)
    sum=((sum%mod)+(R[i]%mod))%mod;

cout<<(sum+pls)%mod;
return 0;
}

Compilation message

automobil.cpp:32:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  main()
       ^

Subtask #1
55.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Incorrect 13 ms 1792 KB Output isn't correct
12 Incorrect 45 ms 5884 KB Output isn't correct
13 Correct 5 ms 512 KB Output is correct
14 Incorrect 47 ms 7020 KB Output isn't correct
15 Incorrect 36 ms 5116 KB Output isn't correct
16 Incorrect 59 ms 8184 KB Output isn't correct
17 Incorrect 59 ms 8276 KB Output isn't correct
18 Incorrect 58 ms 8312 KB Output isn't correct
19 Incorrect 58 ms 8192 KB Output isn't correct
20 Incorrect 59 ms 8192 KB Output isn't correct