oj.uz

Submission #120557

# Submission time Handle Problem Language Result Execution time Memory
120557 2019-06-24T23:20:18 Z _Samir Automobil (COCI17_automobil) C++14
100 / 100
 84 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)%mod))%mod+(m*(m+1)/2)%mod;
   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)%mod+(((n*(n-1)/2)%mod)*m)%mod;
    g%=mod;
    for(auto a:r)
    {
        ll num=((a.F-1)*m)%mod+b.F;
        num%=mod;
        R[a.F]-=num;
        R[a.F]=(R[a.F]+mod)%mod;
        R[a.F]+=(num*b.S)%mod;
        R[a.F]%=mod;
        g-=num;
        g=(g+mod)%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+mod)%mod;
return 0;
}

Compilation message

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

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 8 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 7 ms 384 KB Output is correct
10 Correct 9 ms 384 KB Output is correct
11 Correct 19 ms 1792 KB Output is correct
12 Correct 61 ms 5760 KB Output is correct
13 Correct 7 ms 512 KB Output is correct
14 Correct 54 ms 7040 KB Output is correct
15 Correct 52 ms 5120 KB Output is correct
16 Correct 82 ms 8184 KB Output is correct
17 Correct 83 ms 8184 KB Output is correct
18 Correct 80 ms 8184 KB Output is correct
19 Correct 84 ms 8184 KB Output is correct
20 Correct 83 ms 8312 KB Output is correct