akhauriyash/Code-Regression huggingface dataset:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

INF = float('inf')

def solve():
    n, k = MI()

    ans = 0
    for point in range(1, n+1):
        prob = 1
        while point < k:
            prob = prob / 2
            point = point * 2
        # print(point, prob)
        ans = ans + prob / n

    print(ans)

if __name__ == '__main__':
    solve()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define rep(i, s, e) for (int i = s; i < e; ++i)
#define sort_(a) stable_sort(a.begin(), a.end())
#define rsort(a) stable_sort(a.rbegin(), a.rend())
#define sum(a) accumulate(a.begin(), a.end(), 0LL)
#define join(a, d) accumulate(a.begin() + 1, a.end(), a[0], [](string s, string t) {return s + d + t;})
#define all(a) a.begin(), a.end()
// #define __lcm(a, b) std::__detail::__lcm(a, b)
typedef long long ll;
const long mod = 1e9 + 7;

int main(void) {
#ifdef DEBUG
  freopen("input.txt", "r", stdin);
#endif

  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int N;
  cin >> N;
  vector<int> A1(N + 1, 0);
  vector<int> A2(N + 1, 0);
  rep(i, 1, N + 1) {
    cin >> A1[i];
  }
  rep(i, 1, N + 1) {
    cin >> A2[i];
  }
  vector<int>a1(N + 1);
  vector<int>a2(N + 1);
  partial_sum(all(A1), a1.begin());
  partial_sum(all(A2), a2.begin());
  int ans = 0;
  rep(i, 1, N + 1) {
    ans = max(ans, a1[i] + a2[N] - a2[i-1]);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mod 1000000007
#define mod998 998244353
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define mkp make_pair
typedef long long ll;
using namespace std;

int N, M, p[100000], s[100000], c;
ll w[100000];
tuple<int, int, int>e[100000];

int par(int x) {
	if (p[x] == x)return x;
	else return par(p[x]);
}

void uni(int x, int y) {
	x = par(x);
	y = par(y);
	if (x == y)return;
	if (s[x] >= s[y]) {
		s[x] += s[y];
		w[x] += w[y];
		p[y] = x;
	}
	else {
		s[y] += s[x];
		w[y] += w[x];
		p[x] = y;
	}
}

int main() {
	cin >> N >> M;
	for (int i = 0; i < N; ++i) {
		cin >> w[i];
		s[i] = 1;
		p[i] = i;
	}
	for (int i = 0; i < M; ++i) {
		cin >> get<1>(e[i]) >> get<2>(e[i]) >> get<0>(e[i]);
		--get<1>(e[i]);
		--get<2>(e[i]);
	}
	sort(e, e + M);
	for (int i = 0; i < M; ++i) {
		get<1>(e[i]) = par(get<1>(e[i]));
		get<2>(e[i]) = par(get<2>(e[i]));
		uni(get<1>(e[i]), get<2>(e[i]));
	}
	for (int i = M - 1; i >= 0; --i) {
		if (w[par(get<1>(e[i]))] < get<0>(e[i])) {
			++c;
			int X, Y;
			X = get<1>(e[i]);
			Y = get<2>(e[i]);
			if (s[X] > s[Y])swap(X, Y);
			if (X != Y&&p[X] == Y) {
				p[X] = X;
				while(true) {
					w[Y] -= w[X];
					if (Y == p[Y])break;
					Y = p[Y];
				}
			}
		}
	}
	cout << c << endl;
}


Measured memory_bytes: 2944
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define print(x)cout<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;

int main() {
  int n,k,c;
  cin >> n>> k >> c;
  string s;
  cin>>s;
  vi l(n,-1),r(n,-1);

  int i = 0, cnt = 0;
  while(i<n && cnt<k){
    if(s[i] == 'o'){
      l[i] = cnt;
      cnt++;
      i+=c;
    }
    i++;
  }
  i = n-1; cnt = 0;
  while(i>=0 && cnt<k){
    if(s[i] == 'o'){
      r[i] = k-cnt-1;
      cnt++;
      i-=c;
    }
    i--;
  }
  rep(i,n){
    if(l[i] == r[i] && l[i]!=-1)cout<<i+1<<endl;
  }
  return 0;
}

Measured memory_bytes: 3332
#include <iostream>
using namespace std;
 
int main()
{
  long long n, i, sum;
  cin >> n;
  i = 0;
  sum = 0;
  while(i < n)
  {
    i++;
    if(i % 3 == 0 && i % 5 == 0)
      continue;
    else if(i % 3 == 0)
      continue;
    else if(i % 5 == 0)
      continue;
    else
      sum += i;
  }
  cout << sum;
  return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;

int main(){
	string s;
	int k;
	cin>>k;
	cin>>s;
	for(int i=0;i<s.size();i++){
		if(i>=k){
			cout<<"...";
			break;
		} 
		cout<<s[i];
	}
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,x,values[109],cnt,sum;

int main()
{
    cin>>n>>x;
    for (int i=0;i<n;i++){
       cin>>values[i];
       sum+=values[i];
    }
    if (sum==x)
        cout<<n<<endl;
    else{
        sort(values,values+n);
        for (int i=0;i<n-1;i++){
            if (x-values[i]>=0){
                 cnt++;
                 x-=values[i];
            }
            else
                break;
        }
        if (x==values[n-1])
            cnt++;
        cout<<cnt<<endl;
    }
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

typedef vector<int> vi;
typedef unsigned long long ull;
#define rep(i,a) for(int i=0; i<int(a); i++)

int n, s;
int a[200];
ull dp[2][25];

ull solve(){
    memset(dp, 0, sizeof(dp));
    ull *cur = dp[0], *prev = dp[1];
    prev[a[0]] = 1;
    for (int i = 1; i < n; i++){
        memset(cur, 0, sizeof(dp)/2);
        rep(j, 20 + 1){
            int t1 = j + a[i];
            if (0 <= t1 && t1 <= 20){
                cur[t1] += prev[j];
            }
            int t2 = j - a[i];
            if (0 <= t2 && t2 <= 20){
                cur[t2] += prev[j];
            }
        }
        //rep(i, 21) cout << cur[i] << " ";
        //cout << endl;
        swap(cur, prev);
    }

    return prev[s];
}

int main(){
    while (cin >> n){
        n--;
        rep(i, n) cin >> a[i];
        cin >> s;
        cout << solve() << endl;
    }
}

Measured memory_bytes: 1152
from sys import stdin

if __name__ == "__main__":
  l = [int(i) for i in stdin.readline().split(' ')]
  l = sorted(l)
  if l[0]%2 == l[1]%2:
    ex = 0
  else:
    ex = 2
  print((l[-1]*2 - (l[0] + l[1]))//2 + ex)
  


Measured memory_bytes: 38256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <bits/stdc++.h>
#include <iomanip>
#include <numeric>
#include <utility>
#include <map>
#include <algorithm>
using namespace std;

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    long long N, M;
    cin >> N >> M;
    vector<pair<long long, string>> vec(M);
    set<long long> st2; //不正解
    set<long long> st3; //正解済
    vector<long long> pt(N + 1, 0);
    for (long long i = 0; i < M; ++i)
    {
        long long a;
        string b;
        cin >> a >> b;
        st2.insert(a);
        vec[i].first = a;
        vec[i].second = b;
    }
    long long num_maru = 0, num_pe = 0;
    for (long long i = 0; i < M; ++i)
    {
        if (st3.find(vec[i].first) != st3.end())
            continue;
        if (st2.find(vec[i].first) != st2.end())
        {
            if (vec[i].second == "AC")
            {
                st3.insert(vec[i].first);
                num_maru++;
            }
            else
                pt[vec[i].first]++;
        }
    }
    for (auto i : st3)
        num_pe += pt[i];
    cout << num_maru << " " << num_pe << "\n";
}


Measured memory_bytes: 16640
#include<iostream>
using namespace std;

int main(void){
    int N;
    cin>>N;
    long long int A[N],ans=0,max;
    for(int i=0;i<N;i++){
        cin>>A[i];
    }
    max=A[0];
    for(int i=1;i<N;i++){
        if(A[i]<max){
            ans+=max-A[i];
        }else{
            max=A[i];
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 5180
def examC():
    St = S(); T = S()
    N = len(St) - len(T)
    ans = -1
    for i in range(N,-1,-1):
        cur = 0
        for j in range(len(T)):
            if St[i+j]=="?" or St[i+j]==T[j]:
                cur +=1
                continue
            else:
                break
        if cur==len(T):
            ans =i
            break
    if ans == -1:
        ans="UNRESTORABLE"
    else:
        newS = ""
        for i in range(ans):
            if St[i]=="?":
                newS +="a"
            else:
                newS +=St[i]
        for i in range(ans,ans+len(T)):
            newS += T[i-ans]
        for i in range(ans+len(T),len(St)):
            if St[i]=="?":
                newS +="a"
            else:
                newS +=St[i]
        ans = newS
    print(ans)


import sys,copy,bisect,itertools
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examC()


Measured memory_bytes: 3560
N=int(input())
S=list(input())
a1=[i for i in range(0,(N//2))]
a2=[i for i in range((N//2),N)]
a3=[S[i] for i in a1]
a4=[S[i] for i in a2]
print('Yes' if a3==a4 else 'No')

Measured memory_bytes: 9080
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
const int N=10000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd 998244353
#define eps 1e-8
struct node{
    int to,nxt,cost;
}sq[1001000];
int all=0,head[300300];

struct hnode{
    int u,dis;
};
priority_queue<hnode> q;
bool operator <(hnode p,hnode q)
{
    return p.dis>q.dis;
}
int n,m,dis[300300];
bool vis[300300];

int read()
{
    int x=0,f=1;char ch=getchar();
    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}

void add(int u,int v,int w)
{
    all++;sq[all].to=v;sq[all].nxt=head[u];sq[all].cost=w;head[u]=all;
}

void dij(int s)
{
    rep(i,0,n*3) dis[i]=maxd;
    q.push((hnode){s,0});dis[s]=0;
    while (!q.empty())
    {
        int u=q.top().u;q.pop();
        if (vis[u]) continue;
        vis[u]=1;int i;
        for (i=head[u];i;i=sq[i].nxt)
        {
            int v=sq[i].to;
            if (dis[v]>dis[u]+sq[i].cost)
            {
                dis[v]=sq[i].cost+dis[u];
                if (!vis[v]) q.push((hnode){v,dis[v]});
            }
        }
    }
}

int main()
{
    n=read();m=read();
    rep(i,1,m)
    {
        int u=read(),v=read();
        add((u-1)*3+2,(v-1)*3,1);
        add((u-1)*3,(v-1)*3+1,1);
        add((u-1)*3+1,(v-1)*3+2,1);
    }
    int s=read(),t=read();
    dij((s-1)*3);
    t=(t-1)*3;
    if (dis[t]==maxd) puts("-1");
    else printf("%d",dis[t]/3);
    return 0;
}

Measured memory_bytes: 8448
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double 
const int MAX_N = 1e5 + 5;
const int MAX_L = 20; // ~ Log N
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;


typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef unordered_map<int,int> mii;
typedef unordered_map<char,int> mci;
typedef unordered_map<string,int> msi;

#define pb push_back
#define f first
#define s second 
 

void solve() {
    int n;
    cin>>n;
    vd p(n);
    for(int i=0;i<n;i++) {
        cin>>p[i];
    }
    // n=3;
    // vd p = {0.30,0.60,0.80};
    vvd dp(n+1,vd(n+1));
    dp[0][0] = 1;
    for(int i=1;i<=n;i++) {
        dp[0][i] = 0;
    }
    for(int i=1;i<=n;i++) {
        dp[i][0] = dp[i-1][0]*(1.0 - p[i-1]);
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            dp[i][j] = dp[i-1][j-1]*p[i-1] + dp[i-1][j] * (1.0 - p[i-1]);
        }
    }
    double ans = 0;
    for(int i=n/2+1;i<=n;i++) {
        ans += dp[n][i];
    }
    cout<<setprecision(10);

    cout<<ans<<'\n';
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //#ifdef LOCAL
       // freopen("input.txt", "r", stdin);
        //freopen("output.txt", "w", stdout);
    //#endif

    int tc; tc=1;
    for (int t = 1; t <= tc; t++) {
        //cout << "Case #" << t  << ": ";
        solve();
    }
}

Measured memory_bytes: 144248
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(x,y) for(ll i=x;i<y;i++)
#define tc ll t;cin>>t;while(t--)
#define vll vector<ll>
#define p_b push_back
#define sll set<ll>
int main() {
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
ll i,j,k;
cin>>i>>j>>k;
if(i+j+k>21)
cout<<"bust"<<endl;
else
cout<<"win";
return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;

int main(){
  int N;
  cin >> N;
  set<string> S;
  for(int i=0;i<N;i++){
    string A;
    cin >> A;
    S.insert(A);
  }
  cout << S.size() << endl;
}
  

Measured memory_bytes: 19244
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(){
	int A, B, C, menor = 0, aux = 0, i;
	scanf("%d %d %d", &A, &B, &C);
	menor = B + C;
	aux = C + A;
	if(menor > aux) menor = aux;
	aux = B + A;
	if(menor > aux) menor = aux;
	aux = C + B;
	if(menor > aux) menor = aux;
	printf("%d\n", menor);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define LL long int
#define ULL unsigned long int
#define LD long double

LL MOD = 1000000007;

int main(){
    ULL sum = 0;
    ULL n;
    cin >> n;
    ULL d[100001] = {};
    for(ULL i = 0; i < n; ++i){
        ULL a;
        cin >> a;
        sum += a;
        d[a]++;
    }

    ULL q;
    cin >> q;
    ULL b,c;
    vector<ULL> ans(q);

    for(ULL i = 0; i < q; ++i){
        cin >> b >> c;
        sum -= d[b] * b;
        sum += d[b] * c;
        d[c] += d[b];
        d[b] = 0;
        ans[i] = sum;
    }

    for(ULL i = 0; i < q; ++i) cout << ans[i] << endl;

    return 0;
}

Measured memory_bytes: 4800
S = input()

N = len(S)
k = (N - 1) // 2
ans = True
for i in range(k // 2 + 1):
    if S[i] == S[k - 1 - i] == S[k + 1 + i] == S[2 * k - i]:
        continue
    ans = False
    break
if N == 3 and S[0] != S[2]:
    ans = False
print('Yes' if ans else 'No')


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i,N) for (int i = 0;  i < N; i++)
using namespace std;

int main() {
  int A,B,C,D;
  cin >> A >> B >> C >> D;
  while (min(C,A)>0){
    C=C-B;
    if (C<=0){
      cout << "Yes";
      break;
    }
    A=A-D;
    if (A<=0){
      cout << "No";
      break;
    }
  }  
return 0;
}

Measured memory_bytes: 3624
#include<stdio.h>
int main(void){
int a, b, c, n;
scanf("%d %d %d", &a, &b, &c);
if (a > b){
  n = a;
  a = b;
  b = n;  } 
if (b > c){
  n = b;
  b = c;
  c = n;  }
if (a > b){
  n = a;
  a = b;
  b = n;  }
printf("%d %d %d\n", a, b, c);
return 0;
} 



Measured memory_bytes: 1972
#include<map>
#include<cmath>
#include<stack>
#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
char s[1005];
int main(){
	scanf("%s",s);
	if(strstr(s,"AC")-s>=0)puts("Yes");
	else puts("No");
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define FOR(i,a,b) for(int (i)=(a); (i)<=(b); (i)++)
#define REP(i,N) FOR((i), 0, (N)-1)

int main(){
    char a,b='?';
    cin >> a;
    if(a == 'A')b= 'T';
    if(a == 'T')b= 'A';
    if(a == 'C')b= 'G';
    if(a == 'G')b= 'C';
    cout << b << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
typedef long long ll;

//おいしさの降順、同じ場合は色昇順にソート
bool compare_by_greater_x(pair<ll,int>a, pair<ll,int>b){
    if(a.first!=b.first) return a.first>b.first;
    else return a.second<b.second;
  }

int main(){
  int x,y,a,b,c;cin>>x>>y>>a>>b>>c;
  ll ans=0;
  vector<ll> p(a,0),q(b,0),r(c,0);
  vector<pair<ll,int>> ttl;
  REP(i,a){
    cin>>p.at(i);
    ttl.push_back(make_pair(p.at(i),0));
  }
  sort(p.begin(),p.end(),greater<ll>());
  REP(i,b){
    cin>>q.at(i);
    ttl.push_back(make_pair(q.at(i),1));
  }
  sort(q.begin(),q.end(),greater<ll>());
  REP(i,c){
    cin>>r.at(i);
    ttl.push_back(make_pair(r.at(i),2));
  }
  sort(r.begin(),r.end(),greater<ll>());
  sort(ttl.begin(),ttl.end(),compare_by_greater_x);
  //REP(i,a+b+c) cout<<"i"<<i<<" "<<ttl.at(i).first<<" "<<ttl.at(i).second<<" ";
  //cout<<endl;

  int i=0,lx=0,rx=x,ly=0,ry=y,res=x+y;
  while(res>0){
    //cout<<"i"<<i;
    if((rx==lx&&ttl.at(i).second==0)||(ry==ly&&ttl.at(i).second==1)){
      i++;
      continue;
    }
    if(ttl.at(i).second==0){
      //cout<<" r,"<<p.at(lx);
      ans+=p.at(lx);
      lx++;
    }else if(ttl.at(i).second==1){
      //cout<<" g,"<<q.at(ly);
      ans+=q.at(ly);
      ly++;
    }else{
      //cout<<" tomei,"<<ttl.at(i).first;
      ans+=ttl.at(i).first;
      if(ly==ry||p.at(rx-1)<q.at(ry-1)) rx--;
      else ry--;
    }
    res--;
    i++;
    //cout<<" ans"<<ans<<endl;
  }

  cout<<ans;
}

Measured memory_bytes: 12908
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int r = sc.nextInt();
		int d = sc.nextInt();
		int x2000 = sc.nextInt();

		for(int i=0;i<10;i++) {
			int x = r*x2000-d;
			System.out.println(x);
			x2000 = x;
		}

		sc.close();

	}

}


Measured memory_bytes: 23124
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(i=a;i<=b;i++)
using namespace std;
const int mod=1e9+7;
const int N=2010,M=4000100;
const int maxn=4000000;
int dp[N*2][N];
int cj[M],inv[M];
int ans;

int C(int n,int m){
	return 1ll*cj[n]*inv[m]%mod*inv[n-m]%mod;
}

int power(int x,int y){
	int ret=1;
	for(;y;y>>=1,x=1ll*x*x%mod){
		if(y&1)	ret=1ll*ret*x%mod;
	}
	return ret;
}

int main(){
	//freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
	register int n,K,i,j,k;
	scanf("%d%d",&n,&K);
	if(K==1){printf("1\n");return 0;}
	for(cj[0]=1,i=1;i<=maxn;i++)	cj[i]=1ll*cj[i-1]*i%mod;
	inv[maxn]=power(cj[maxn],mod-2);inv[0]=1;
	for(i=maxn-1;i;i--)	inv[i]=1ll*inv[i+1]*(i+1)%mod;
	dp[0][0]=1;
	rep(i,0,2*n-1)	rep(j,0,n)	if(dp[i][j]){
		k=(i-j)/2;
		dp[i+1][j+1]=(dp[i+1][j+1]+dp[i][j])%mod;		
		if(j)	dp[i+1][j-1]=(dp[i+1][j-1]+1ll*dp[i][j]*C(n*K-i-1-(K-2)*k,K-2))%mod;
	}
	ans=1ll*dp[2*n][0]*cj[n]%mod;
	printf("%d\n",ans);
}

Measured memory_bytes: 62848
s=list(str(input()))

x=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]

S = set(sorted(s))

result=list(set(x)-set(S))

result=sorted(result)

if len(result)==0:
    print("None")
else:
    print(result[0])


Measured memory_bytes: 5100
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<long>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvb = vector<vector<bool>>;
using vvc = vector<vector<char>>;
using vvl = vector<vector<long>>;
using pii = pair<int, int>;
using pil = pair<int, long>;
using pll = pair<long, long>;
#define fix20 cout << fixed << setprecision(20)
#define YES cout << "Yes" << endl
#define NO cout << "No" << endl
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define REP(i,s,t) for(int i=s; i<t; i++)
#define RNG(i,s,t,u) for(int i=s; i<t; i+=u)
#define MOD 1000000007
#define all(vec) vec.begin(), vec.end()

int main(){
  int a,b;
  cin >> a >> b;
  cout << a*b << endl;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;


typedef long long ll;
typedef pair<int, int> P;

struct edge {int to; ll cost; };

int dx[] = {-1, 1, 0,  0};
int dy[] = { 0, 0, 1, -1};
 
int main(){
  int n, k;
  cin >> n >> k;
  int s[3];
  for(int i=0; i<3; i++) cin >> s[i];
  string t;
  cin >> t;
  int ans = 0;
  for(int i=0; i<n; i++){
    if(i/k){
      if(t[i-k]==t[i]){
        t[i] = 'x';
        continue;
      }
      if(t[i]=='r') ans += s[2];
      else if(t[i]=='s') ans += s[0];
      else ans += s[1];
    }else{
      if(t[i]=='r') ans += s[2];
      else if(t[i]=='s') ans += s[0];
      else ans += s[1];
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3740
#include <bits/stdc++.h>
using namespace std;
const long long INF = 123456789;
const long long MOD = 1000000007;
const long double PI = 3.1415926;
#define FOR(i, r, n) for (ll i = (ll)(r); i < (ll)(n); i++)
#define RFOR(i, r, n) for (ll i = (ll)(n - 1); i >= r; i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()
typedef long long int ll;
typedef vector<ll> vi;
typedef vector<pair<ll, ll>> vp;
typedef vector<string> vs;
typedef vector<char> vc;
typedef list<ll> lst;

ll n, m, k, ans = 0, sum = 0, cnt = 0;
string s;
char c;

#define Endl endl

/*--------------------template--------------------*/

int main()
{
    cin >> s;
    ans = s.size();
    for (int i = 0; i < s.size() - 1;++i){
        if(s[i]!=s[i+1]){
            ans=min<ll>(ans,max<ll>(i+1,s.size()-(i+1)));
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 512
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder.ABC._125
{
    class A
    {
        static void Solve()
        {
            int[] inputs = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            Console.WriteLine(inputs[2]/inputs[0]*inputs[1]);
        }

        static void Main()
        {
            Solve();
        }
    }
}


Measured memory_bytes: 13268
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<bool> P(100001, true);
    P[0] = P[1] = false;
    for (int i=2; i<=100000; i++)
        if (P[i])
            for (int j=i+i; j<=100000; j+=i)
                P[j] = false;

    vector<int> S(100001);
    for (int i=1; i<=100000; i++)
        if (i%2!=0 && P[i] && P[(i+1)/2])
            S[i] = S[i-1]+1;
        else
            S[i] = S[i-1];

    int Q;
    cin>>Q;
    for (int i=0; i<Q; i++)
    {
        int l, r;
        cin>>l>>r;
        cout<<S[r]-S[l-1]<<endl;
    }
}


Measured memory_bytes: 1024
#include "bits/stdc++.h"
#define MOD 1000000007
#define INF 11234567890
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

int a, b, h;

int main()
{
	in >> a >> b >> h;

	out << (a + b)*h / 2 << std::endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

#define rep(i, n) for(int i=0;i<(int)(n);i++)

using namespace std;

int main() {
    string S;
    cin >> S;

    int a = 700;
    if (S[0] == 'o') {
        a += 100;
    }
    if (S[1] == 'o') {
        a += 100;
    }
    if (S[2] == 'o') {
        a += 100;
    }
    cout << a << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;

int main() {
  ll N;
  vector<ll> A(5);
  cin >> N;
  rep(i,5) cin >> A[i];
  ll s = A.size();
  ll ans = 0;
  rep(i,5) {
    ll res = (N + (A[i]-1)) / A[i];
    ans = max(ans, res+s-1);
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
//"BISMILLAHIR RAHMANIR RAHIM"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
const long long M = 1e8 ;
int main()
{
    int d,t,s;
    cin>>d>>t>>s;

    ll ans= (100000*d/s);
    if(ans<=(t*100000))
      cout<<"Yes"<<endl;
    else
      cout<<"No"<<endl;
    return 0;
}



Measured memory_bytes: 3644
from collections import deque
H, W = map(int, input().split())
G = [list(input()) for i in range(H)]

black = 0
for h in range(H):
    for w in range(W):
        black += (G[h][w] == "#")

que = deque()
que.append([0, 0, 0])
direction = [(0, 1), (0, -1), (1, 0), (-1, 0)]

visited = set([(0, 0)])
while que:
    nh, nw, cost = que.pop()
    G[nh][nw] = cost
    if G[H - 1][W - 1] != ".":
        print(H * W - black - int(G[H - 1][W - 1]) - 1)
        break

    for dh, dw in direction:
        if (0 <= nh + dh < H) & (0 <= nw + dw < W):
            if G[nh + dh][nw + dw] == "." and (nh + dh, nw + dw) not in visited:
                que.appendleft((nh + dh, nw + dw, cost + 1))
                visited.add((nh + dh, nw + dw))
else:
    print(-1)


Measured memory_bytes: 3700
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int d = sc.nextInt();
        int n = sc.nextInt();

        if(d ==0){
            System.out.println((n/100)+n);
        }else if(d==1){
            System.out.println((n/100)*100+n*100);
        }else{
            System.out.println((n/100)*10000+n*10000);
        }
        
    }
}


Measured memory_bytes: 23124
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;

int MOD=1e9+7;
ll INF=1e18;

int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};

int main(){
    int n; cin>>n; 
    vector<int> imos(100010, 0);
    for(int i=0; i<n; i++){
        int l, r; cin>>l>>r;
        imos[l]++, imos[r+1]--;
    }

    for(int i=1; i<=100000; i++){
        imos[i]+=imos[i-1];
    }

    int ans=0;
    for(int i=1; i<=100000; i++){
        if(imos[i]>0) ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 640
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int a = input.nextInt();
        int b = input.nextInt();
        int c = input.nextInt();
        int counter = 0;
        for(int i = a; i <= b; i++){
            if(c % i == 0) counter++;
        }
        System.out.println(counter);
    }
}



Measured memory_bytes: 26416
# 解説

def solve() -> bool:
    n, a, b, c, d = map(int, input().split())
    return any((n - 1 - m) * c - m * d <= b - a <= (n - 1 - m) * d - m * c for m in range(n - 1))


print('YES' if solve() else 'NO')


Measured memory_bytes: 39408
#include <iostream>
#include <map>

using namespace std;

#define MN 101

int n;
int ks[MN];
string raw;

map<char, int> kmap;
map<int, char> rkmap;

void init_() {
    for (char i = 'a'; i <= 'z'; i++) {
        kmap[i] = i - 'a';
        rkmap[i - 'a'] = i;
    }
    for (char i = 'A'; i <= 'Z'; i++) {
        kmap[i] = i - 'A' + 26;
        rkmap[i - 'A' + 26] = i;
    }
}

bool init() {
    cin >> n;
    if (n == 0) return false;
    for (int i = 0; i < n; i++) {
        cin >> ks[i];
    }
    cin >> raw;
    return true;
}

char before(char r, int b) {
    int i = kmap[r];
    return rkmap[(i + 52 - b) % 52];
}

void solve() {
    string ans = raw;
    int kindex = 0;
    for (int i = 0; i < raw.size(); i++) {
        ans[i] = before(raw[i], ks[kindex]);
        kindex = (kindex + 1 + n) % n;
    }
    cout << ans << endl;
}

int main() {
    init_();
    while (init()) {
        solve();
    }
    return 0;
}

Measured memory_bytes: 1216
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        while(true){
        int m = sc.nextInt();
        int f = sc.nextInt();
        int r = sc.nextInt();
        

        if(m == -1 && f == -1 && r == -1){
            break;
        }
            if(m == -1 || f == -1){
            System.out.println("F");
        }else{
            if(m + f >= 80){
                System.out.println("A");
            }else if(m + f >= 65){
                System.out.println("B");
            }else if(m + f >= 50){
                System.out.println("C");
            }else if(m + f >= 30){
                if(r >= 50){
                    System.out.println("C");
                }else{
                    System.out.println("D");
                }
            }else{
                System.out.println("F");
                }
            }
        }
        sc.close();
    }
}


Measured memory_bytes: 26096
#include <bits/stdc++.h>
using namespace std;
using P=pair<int,int>;
using ll=long long;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    long double d;
    cin>>n>>d;
    vector<ll> x(n);
    vector<ll> y(n);
    int ans=0;
    for(int i=0;i<n;i++){
        cin>>x[i]>>y[i];
        ll a=x[i]*x[i]+y[i]*y[i];

        if(sqrt(a)<=d) ans++;

    }
    cout<<ans<<endl;


    
}

Measured memory_bytes: 6436
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::pair<long long int, int>> inp(n);
    for (int i = 0; i < n; i++) {
        std::cin >> inp[i].first >> inp[i].second;
    }
    std::sort(inp.begin(), inp.end());
    long long int ans = 0;
    for (auto x : inp) {
        if (m < x.second) {
            ans += x.first * m;
            break;
        } else {
            ans += x.first * x.second;
            m -= x.second;
        }
    }
    std::cout << ans << std::endl;
}

Measured memory_bytes: 1920
import java.util.*;
public class Main {
        public static void main(String[] args){
                // 初期化
                int ac=0;
                int wa=0;
                int tle=0;
                int re=0;

                Scanner sc = new Scanner(System.in);
                // 整数の入力
                int n = sc.nextInt();
                // ループ
                for (int i=0; i<n; i++) {
                        // 文字列の入力
                        String s = sc.next();
                        if (s.equals("AC")) {ac++;}
                         else if (s.equals("WA")) {wa++;}
                         else if (s.equals("TLE")) {tle++;}
                         else if (s.equals("RE")) {re++;}
                }
                // 出力
                System.out.println("AC x " + ac);
                System.out.println("WA x " + wa);
                System.out.println("TLE x " + tle);
                System.out.println("RE x " + re);

        }
}


Measured memory_bytes: 58456
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define L 12
#define N 1000000

char H[N][L];

int getChar(char);
long long getKey(char *);
int h1(int);
int h2(int);
int find(char *);
int insert(char *);


int main(void){
  char cmd[7],str[L];
  int n;
  int i;
  for(i = 0; i < N; i++) H[i][0] = '\0';

  scanf(" %d",&n);
  for(i = 0; i < n; i++){
    scanf(" %s %s",cmd,str);
    if(cmd[0] == 'i'){
      insert(str);
    }
    else if(cmd[0] == 'f'){
      if(find(str)) printf("yes\n");
      else printf("no\n");
    }
    else{
      fprintf(stderr,"Invalid command is included\n");
      exit(0);
    }
  }
  
  return 0;
}

int getChar(char ch){
  if(ch == 'A') return 1;
  else if(ch == 'C') return 2;
  else if(ch == 'G') return 3;
  else if(ch == 'T') return 4;
}

long long getKey(char *str){
  long long sum=0,p=1,i;
  for(i = 0; i < strlen(str); i++){
    sum += p*(getChar(str[i]));
    p *= 5;
  }
  return sum;
}

int h1(int key){
  return key % N;
}

int h2(int key){
  return 1 + key % (N-1);
}

int find(char *str){
  long long key,t,i;

  key = getKey(str);

  for(i = 0;; i++){
    t = (h1(key) + i * h2(key)) % N;
    if(strcmp(H[t],str) == 0) return 1;
    else if(strlen(H[t]) == 0) return 0;
  }
  return 0;
}

int insert(char *str){
  long long key,t,i;

  key = getKey(str);

  for(i = 0;; i++){
    t = (h1(key) + i * h2(key)) % N;
    if(strcmp(H[t],str) == 0) return 1;
    if(strlen(H[t]) == 0){
      strcpy(H[t],str);
      return 0;
    }
  }
  return 0;
}



Measured memory_bytes: 13504
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int h = in.nextInt();
		int w = in.nextInt();
		char[][] map = new char[h][w];
		int[][] hmap = new int[h][w]; // 横方向
		int[][] vmap = new int[h][w]; // 縦方向

		for ( int i = 0; i < h; i++ ) {
			map[i] = in.next().toCharArray();
		}
		in.close();

		int cnt = 0;
		// 横の処理
		for ( int r = 0; r < h; r++ ) {			
			for ( int c = 0; c < w; c++ ) {
				cnt = 0;
				while ( c + cnt < w && map[r][c + cnt] == '.' ) {
					cnt++;
				}
				for ( int i = c; i < c + cnt; i++ ) {
					hmap[r][i] = cnt;
				}
				c += cnt;
			}
		}

		// 縦の処理
		for ( int c = 0; c < w; c++ ) {
			cnt = 0;
			for ( int r = 0; r < h; r++ ) {
				if ( map[r][c] == '.' ) {
					cnt++;
					vmap[r][c] = cnt;
				} else if ( map[r][c] == '#' ) {
					cnt = 0;
				}
			}

			for ( int r = h - 2; 0 <= r; r-- ) {
				if ( map[r][c] == '#' ) {
					continue;
				} else if ( map[r + 1][c] == '.' ) {
					vmap[r][c] = vmap[r + 1][c];
				}
			}
		}

		int ans = 0;
		for ( int r = 0; r < h; r++ ) {
			for ( int c = 0; c < w; c++ ) {
				ans = Math.max(ans, hmap[r][c] + vmap[r][c] - 1);
			}
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 116340
package main

import (
	"fmt"
)

var N, K int

func main() {
	fmt.Scanf("%d %d", &N, &K)

	if K == 0 {
		fmt.Println(N * N)
		return
	}

	ans := 0
	for b := K + 1; b <= N; b++ {
		ans += (N / b) * (b - K)
		if N%b >= K {
			ans += N%b - K + 1
		}
	}

	fmt.Println(ans)
}


Measured memory_bytes: 512
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <random>
#include <complex>
#include <assert.h>

using namespace std;
typedef long long ll;

const ll INF = 1LL << 60;

template<typename T>
inline bool chmin(T& x, T a) {
	if (x >= a) { x = a; return true; }
	return false;
}

template<typename T>
inline bool chmax(T& x, T a) {
	if (x <= a) { x = a; return true; }
	return false;
}

bool f[100][100];
bool reach[100][100];

int main() {
	int H, W; cin >> H >> W;
	const char table[4][4] = {
		{'6', '3', '1', '4'},
		{'2', '0', '2', '0'},
		{'1', '3', '6', '4'},
		{'5', '0', '5', '0'}
	};
	
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			reach[i][j] = false;
			f[i][j] = false;
			char c; cin >> c;
			f[i][j] = (c == table[i % 4][j % 4]);
		}
	}

	queue<pair<int, int>> q;
	q.push({ 0,0 });
	reach[0][0] = true;

	while (q.size() != 0) {
		pair<int, int> p = q.front();
		q.pop();

		int i = p.first, j = p.second;
		if (i < H - 1 && f[i + 1][j] == true) {
			if (reach[i + 1][j] == false) {
				q.push({ i + 1, j });
				reach[i + 1][j] = true;
			}
		}
		if (i > 0 && f[i - 1][j] == true) {
			if (reach[i - 1][j] == false) {
				q.push({ i - 1, j });
				reach[i - 1][j] = true;
			}
		}
		if (j < W - 1 && f[i][j + 1] == true) {
			if (reach[i][j + 1] == false) {
				q.push({ i, j + 1 });
				reach[i][j + 1] = true;
			}
		}
		if (j > 0 && f[i][j - 1] == true) {
			if (reach[i][j - 1] == false) {
				q.push({ i, j - 1 });
				reach[i][j - 1] = true;
			}
		}
	}

	if (reach[H - 1][W - 1] == true) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}

	return 0;
}


Measured memory_bytes: 3168
#include <bits/stdc++.h>
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int h, w, k;
  cin >> h >> w >> k;
  
  vector<vector<char>> c(h, vector<char>(w));
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      cin >> c.at(i).at(j);
    }
  }
  
  int ans = 0;
  for (int biti = 0; biti < (1 << h); biti++) {
    for (int bitj = 0; bitj < (1 << w); bitj++) {
      vector<vector<char>> x = c;
      for (int i = 0; i < h; i++) {
        if (biti & (1 << i)) {
          for (int j = 0; j < w; j++) {
            x.at(i).at(j) = '.';
          }
        }
      }
      for (int j = 0; j < w; j++) {
        if (bitj & (1 << j)) {
          for (int i = 0; i < h; i++) {
            x.at(i).at(j) = '.';
          }
        }
      }
      int count = 0;
      for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
          if (x.at(i).at(j) == '#') count++;
        }
      }
      if (count == k) ans++;
    }
  }
  
  cout << ans << '\n';
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, int>;

ll solve() {
    ll N;
    cin >> N;
    vector<ll> P(N);
    vector<pii> pp(N);
    for ( int i = 0; i < N; i++ ) {
        cin >> P[i];
        pp[i] = pii(P[i], i);
    }
    sort(pp.begin(), pp.end());
    vector<int> l1(N, -1), l2(N, -1), r1(N, N), r2(N, N);
    set<int> s;
    for ( int j = N-1; j >= 0; j-- ) {
        ll p = pp[j].first;
        int i = pp[j].second;
        auto u0 = s.upper_bound(i);
        auto u = u0;
        if ( u != s.end() ) {
            r1[i] = *u;
            u++;
            if ( u != s.end() ) {
                r2[i] = *u;
            }
        }
        u = u0;
        if ( u != s.begin() && !s.empty() ) {
            u--;
            l1[i] = *u;
            if ( u != s.begin() ) {
                u--;
                l2[i] = *u;
            }
        }
        s.insert(i);
   }
    ll ans = 0;
    for ( int i = 0; i < N; i++ ) {
        ans += (l1[i] - l2[i]) * (r1[i] - i) * P[i];
        ans += (i - l1[i]) * (r2[i] - r1[i]) * P[i];
    }
    return ans;
}

int main() {
    auto ans = solve();
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 8832
import sys

stdin = sys.stdin

ns = lambda : stdin.readline().rstrip()
ni = lambda : int(ns())
na = lambda : map(int, stdin.readline().split())

def divi(n):
  res = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      res.append(i)
      if i != n // i:
        res.append(n // i)
  return res

def isprime(n):
  if n == 2:
    return True
  if n % 2 == 0 or n < 2:
    return False
  for i in range(3, int(n**0.5)+1, 2):
    if (n % i == 0):
      return False
  return True

def main():
  a, b = sorted(na())
  x = divi(a)
  cnt = 1
  for bb in divi(b):
    if bb in x and isprime(bb):
      cnt += 1
  print(cnt)
main()

Measured memory_bytes: 3500
#include <bits/stdc++.h>
#define rep(i,n) for(long long i=0; i<n; i++)
#define Rep(i,n) for(long long i=1; i<n; i++)
#define ll long long
#include <math.h>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <queue>
#include <set>
#include <vector>


using namespace std;
#define PI acos(-1)
using P =pair<ll,ll>;

ll ketasu(ll a){
   ll num=1;
   while(a/10){
       num++;
       a/=10;
   }
   return num;
}

ll gcd(ll a,ll b){return b ? gcd(b,a%b) :a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}

ll kosuu(ll a){
    ll sum=0;
    for(ll i=1;i*i<=a;i++){
        if(a%i==0){
            if(a!=1&&i*i!=a){
            sum+=2;
            }else{
             sum++;   
            }
        }
    }
    return sum;
}

ll n;



    vector<pair<ll,ll>>p;
void fs(ll a){
    for(ll i=2;i*i<=n;i++){
        ll cnt=0;
        while(n%i==0){
            n/=i;
            cnt++;
        }
        p.emplace_back(i,cnt);
    }
    return;
}


ll di[]={1,0,-1,0};
ll dj[]={0,-1,0,1};
int main()
{
 const ll m=1000000007;
 ll n;
 cin>>n;
 ll a[n];
 rep(i,n)cin>>a[i];
 ll sum=0;
 rep(i,n)sum+=a[i];
 ll ans=0;
 rep(i,n){
         sum=sum-a[i];
         ans+=(sum%m * a[i]%m)%m;
         ans%=m;
 }
 cout<<ans%m<<endl;
 return 0;
 
}
 




Measured memory_bytes: 5160
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep1(i, n) for(int i = 1; i < n+1; i++)
#define sort(A) sort(A.begin(),A.end())
#define reverse(A) reverse(A.begin(),A.end());
#define vecmin(A) *min_element(A.begin(),A.end());
#define vecmax(A) *max_element(A.begin(),A.end());
typedef long long ll;

int main(){
  int a,b;
  cin >> a >> b;
  if(a+b >= 10) cout << "error" << endl;
  else cout << a+b << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
using ll = long long;

int main() {
    int X,Y,Z,K;
    cin >> X >> Y >> Z >> K;
    vector<ll>A(X);
    vector<ll>B(Y);
    vector<ll>C(Z);
    for (int i = 0; i < X; ++i) cin >> A[i];
    for (int i = 0; i < Y; ++i) cin >> B[i];
    for (int i = 0; i < Z; ++i) cin >> C[i];

    sort(A.begin(), A.end(), greater<ll>());
    sort(B.begin(), B.end(), greater<ll>());
    sort(C.begin(), C.end(), greater<ll>());

    priority_queue<vector<ll>> q;
    q.push({A[0]+B[0]+C[0],0,0,0});

    // std::set を使ってフラグ管理をすればいいらしい
    set<tuple<int,int,int>> se;

    for (int i = 0; i < K; ++i){
        cout << q.top()[0] << endl;
        ll qx = q.top()[1];
        ll qy = q.top()[2];
        ll qz = q.top()[3];
        q.pop();

        if(qx+1 < X){
            tuple<int,int,int> t = make_tuple(qx+1,qy,qz);
            if(!se.count(t)){
                se.insert(t);
                q.push({A[qx+1] + B[qy] + C[qz], qx+1, qy, qz});
            }
        }
        if(qy+1 < Y) {
            tuple<int,int,int> t = make_tuple(qx,qy+1,qz);
            if(!se.count(t)){
                se.insert(t);
                q.push({A[qx] + B[qy+1] + C[qz], qx, qy+1, qz});
            }
        }
        if(qz+1 < Z) {
            tuple<int,int,int> t = make_tuple(qx,qy,qz+1);
            if(!se.count(t)){
                se.insert(t);
                q.push({A[qx] + B[qy] + C[qz+1], qx, qy, qz+1});
            }
        }
    }
    return 0;
}

Measured memory_bytes: 1152
def Int():
    return int(input())
def Ints():
    return map(int,input().split())
def IntList():
    return list(Ints())
def IntMat(N):
    return [IntList() for i in range(N)]

import sys
sys.setrecursionlimit(4100000)
rl = sys.stdin.readline

s = input()
t = input()

flag = 1
l = len(s)

for i in range(l):
    if s[i]!=t[i]:
        flag = 0
        break
        
if flag == 1:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 61744
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
#define MAX 1000005
int main(){
  bool e[2][MAX]={{}};
  //P s[2][MAX];
  //int sx[2][MAX]={{}};
  //int sy[2][MAX]={{}};
  int st[2][500][500]={{{}}};
  int n,u,v,m;
  int i,j,k;
  cin >> n >> u >> v >> m;
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      cin >> k;
      e[0][k]=true;
      st[0][i][j]=k;
    }
  }
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      cin >> k;
      e[1][k]=true;
      st[1][i][j]=k;
    }
  }
  int col[2][500]={{}};
  int row[2][500]={{}};
  bool bcol[2][500]={{}};
  bool brow[2][500]={{}};
  int nnm[2][2]={{}};
  bool bnnm[2][2]={{}};
  int c[2]={};
  int ans=0;
  int x,y;
  for(i=0;i<m;i++){
    cin >> k;
    for(j=0;j<2;j++){
      if(e[j][k]){
	x=-1;
	for(int a=0;a<n;a++){
	  for(int b=0;b<n;b++){
	    if(st[j][a][b]==k){
	      x=a;y=b;break;
	    }
	  }
	  if(x!=-1) break;
	}
	if(!bcol[j][x]){
	  col[j][x]++;
	  if(col[j][x]==n){
	  c[j]++;
	  bcol[j][x]=true;
	  }
	}
	if(n>1){
	  if(!brow[j][y]){
	    row[j][y]++;
	    if(row[j][y]==n){
	      c[j]++;
	      brow[j][y]=true;
	    }
	  }
	  if(!bnnm[j][0]){
	    if(x==y) nnm[j][0]++;
	    if(nnm[j][0]==n){
	      c[j]++;
	      bnnm[j][0]=true;
	    }
	  }
	  if(!bnnm[j][1]){
	    if(x+y+1==n) nnm[j][1]++;
	    if(nnm[j][1]==n){
	      c[j]++;
	      bnnm[j][1]=true;
	    }
	  }
	}
      }
    }

    //cout << k <<":"<< c[0] << c[1] << endl;
    if(u<=c[0]&&v<=c[1]){
      break;
    }else if(u<=c[0]){
      ans=1;
      break;
    }else if(v<=c[1]){
      ans=2;
      break;
    }
      
  }
  if(ans==0) cout << "DRAW"  << endl;
  if(ans==1) cout << "USAGI" << endl;
  if(ans==2) cout << "NEKO"  << endl;
  return 0;
}

Measured memory_bytes: 5080
#include <bits/stdc++.h>
#define rep(i,n) for(int64_t i=0;i < (int64_t)(n);i++)
#define invrep(i,n) for(int64_t i=n-1;i >= 0;i--)
#define _GLIBCXX_DEBUG
using namespace std;

int main(){
  int64_t n;
  cin >> n;
  vector<pair<int64_t,int64_t>> a(n);
  rep(i,n){
    int64_t hoge;
    cin >> hoge;
    a[i] = make_pair(hoge,i+1);
  }
  int64_t cnt=0;
  sort(a.begin(),a.end());
  rep(i,n){
    a[i].first = i+1;
    //cout << a[i].first << " " << a[i].second << endl;
    if(a[i].first % 2 != a[i].second % 2 ){
      cnt++;
    }
  }
  cout << cnt/2 << endl;
      
  
    
}

Measured memory_bytes: 1792
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using System.Numerics;
using System.IO;
using System.Runtime.InteropServices;
using static System.Math;
using static io;
public class CompetitiveProgramming
{
  public void Solve()
  {
    var ll = new LinkedList<int>();
    var N = Int1;
    for (int i = 0; i < N; ++i)
    {
      var o = Strs;
      if (o[0] == "insert")
      {
        ll.AddFirst(int.Parse(o[1]));
      }
      else if (o[0] == "delete")
      {
        ll.Remove(int.Parse(o[1]));
      }
      else if (o[0] == "deleteFirst")
      {
        //Write(ll.First());
        ll.RemoveFirst();
      }
      else if (o[0] == "deleteLast")
      {
        //Write(ll.Last());
        ll.RemoveLast();
      }
    }
    while (ll.Any())
    {
      Console.Write(ll.First());
      if (ll.Count > 1) Console.Write(" ");
      ll.RemoveFirst();
    }
    Console.Write("\n");
  }
}



class Program
{
  static void Main(string[] args)
  {
    var CompetitiveProgramming = new CompetitiveProgramming();
    CompetitiveProgramming.Solve();
  }
}
public static class io
{
  public static string Str => Console.ReadLine();
  public static string[] Strs => Str.Split(' ');
  public static long[] Longs => Strs.Select(long.Parse).ToArray();
  public static int[] Ints => Strs.Select(int.Parse).ToArray();
  public static char[] Chars => Str.ToArray();
  public static double[] Doubles => Strs.Select(double.Parse).ToArray();
  public static long Long1 => Longs[0];
  public static int Int1 => Ints[0];
  public static char Char1 => Chars[0];
  public static double Double1 => Doubles[0];
  public static long[] VerticalRead(int N) { long[] A = new long[N]; for (int i = 0; i < N; ++i) A[i] = Long1; return A; }
  public static void Write(string a) => Console.WriteLine(a);
  public static void Write(params object[] i) => Write(string.Join(" ", i));
  public static void Write<T>(IEnumerable<T> a) => Write(string.Join(" ", a));
  public static void Verticalwrite<T>(IEnumerable<T> a) { foreach (var z in a) Write(z); }
  public static void YN(bool i) { if (i) Write("Yes"); else Write("No"); }
}



Measured memory_bytes: 73732
n = int(input())
plan = [list(map(int, input().split())) for i in range(n)]

t0 = 0
x0 = 0
y0 = 0

for t, x, y in plan:
    if not (abs(x-x0) + abs(y-y0) <= (t-t0) and (t-t0)%2 == (abs(x-x0) + abs(y-y0))%2):
        print("No")
        exit()
    t0 = t
    x0 = x
    y0 = y

print("Yes")

Measured memory_bytes: 27380
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define fop(i,m,n) for (int i=(m);i<(n);i++)
#define FOP(i,m,n) for (int i=(m)-1;i>=(n);--i)
#define test(x) cout << #x << ' ' << x << endl;
#define eb emplace_back
#define pb push_back
#define mp make_pair 
#define pii pair<int,int>
#define X first
#define Y second 

int main () {
    int n;
    cin >> n;
    int input[n][n];
    fop (i,0,n) fop (j,0,n) cin >> input[i][j];
    lli sum[1 << n], dp[1 << n];
    dp[0] = sum[0] = 0;
    fop (s,1,1 << n) {
        vector <int> v;
        dp[s] = sum[s] = 0;
        fop (i,0,n) if (s & (1 << i)) v.pb(i);
        fop (i,0,v.size()) {
            fop (j,i+1,v.size()) {
                sum[s] += input[v[i]][v[j]];
            }
        }
        dp[s] = sum[s];
    }
    fop (s,0,1 << n) {
        int now = s;
        while (now > 0) {
            dp[s] = max(dp[s], dp[s ^ now] + sum[now]);
            now = (now - 1) & s;
        }
    }
    cout << dp[(1 << n) - 1] << endl;
}

Measured memory_bytes: 1280