akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i=0,i##_cond=(n);i<i##_cond;++i)
using vi  = vector<int>;
using vvi = vector<vi>;
constexpr int inf = 1<<30;
template<class T>bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;}

using Cost = int;
class node {
public:
  int v;
  Cost d;
  node(int _a, Cost _b):v(_a),d(_b){}
  bool operator<(const node &n) const { return d > n.d; }
};
class edge {
public:
  int to;
  Cost d;
  edge(){}
  edge(int _to, Cost _d):to(_to),d(_d){}
};
class dijkstra{
public:
  vector<vector<edge>> G;
  vector<Cost> dist;

  dijkstra(int s,const vector<vector<edge>> &_G):G(_G){ // sからの最短経路
    dist.resize(G.size(),inf);
  
    priority_queue<node> que;
    que.push(node(s, 0));
    dist[s] = 0;
    
    while(!que.empty()){
      int v = que.top().v;
      Cost d = que.top().d;
      que.pop();
      
      rep(i, G[v].size()){
	Cost tmp = d + G[v][i].d;
	if(dist[G[v][i].to] > tmp){
	  dist[G[v][i].to] = tmp;
	  que.push(node(G[v][i].to, tmp));
	}
      }
    }
  }
};

signed main(){
  int N, M, H, K;
  while(cin >> N >> M >> H >> K, N){
    // input
    vvi e(M,vi(5));
    rep(i,M){
      rep(j,5) cin >> e[i][j];
      e[i][0]--;
      e[i][1]--;
      e[i][4]--;
    }
    int S, T, P; cin >> S >> T >> P; S--; T--;
    vi d(P);
    vvi k(P);
    rep(i,P){
      int l;
      cin >> l >> d[i];
      k[i].resize(l);
      rep(j,l){
	cin >> k[i][j];
	k[i][j]--;
      }
    }

    // 1 day passで作れる集合を求める
    vvi dp(1<<K,vi(P+1,inf));
    rep(j,P+1) dp[0][j] = 0;
    vi bitk(P); // kのbit表現
    rep(i,P) rep(j,k[i].size()) bitk[i] += 1<<k[i][j];
    rep(i,1<<K) rep(j,P){
      chmin(dp[i][j+1],dp[i][j]); // j番目を使わない時
      int next = i | bitk[j];
      chmin(dp[next][j+1], dp[i][j] + d[j]); // j番目を使うとき
    }

    // 作れる集合ごとに最小コストを求める
    int ans = inf;
    rep(i,1<<K){
      if(dp[i][P] == inf) continue; // 作れない

      // 拡張グラフ構築
      vector<vector<edge>> g(N*(H+1));
      rep(j,M){
	int a = e[j][0], b = e[j][1], c = e[j][2], h = e[j][3], r = e[j][4];
	if((i>>r)&1) c = 0;
	rep(l,H-h+1){ // スタート時間
	  g[l*N+a].emplace_back((l+h)*N+b, c);
	  g[l*N+b].emplace_back((l+h)*N+a, c);	    
	}
      }

      dijkstra dijk(S, g);
      rep(j,H+1)
	chmin(ans, dijk.dist[j*N+T]+dp[i][P]);
    }
    if(ans == inf) cout << -1 << endl;
    else cout << ans << endl;
  }
}


Measured memory_bytes: 3784
package main

import (
	"fmt"
	"sort"
)


func main() {

	var n int
	fmt.Scan(&n)
	cards:=make([]int,n)

	for i:=range cards{
		fmt.Scan(&cards[i])
	}
	sort.Sort(sort.Reverse(sort.IntSlice(cards)))
	
	var a,b int
	var turn int
	for _,c:=range cards{
		if turn%2==0{
			a+=c
		}else{
			b+=c
		}
		turn++
	}

	fmt.Println(a-b)
}

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

#define REP(i,n) for(int i=0; i < (n); ++i)
#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)

using ll = long long;
#define INF 1e9

int N, C;
vector<vector<int>> D, c;
vector<vector<int>> cnt;
int main(){
  cin >> N >> C;
  D.resize(C, vector<int>(C)), c.resize(N, vector<int>(N));
  cnt.resize(3, vector<int>(C, 0));
  REP(i, C){
    REP(j, C){
      cin >> D[i][j];
    }
  }
  REP(i, N){
    REP(j, N){
      cin >> c[i][j];
      c[i][j]--;
    }
  }
 REP(i, N){
   REP(j, N){
     cnt[(i+1+j+1)%3][c[i][j]]++;
   }
 }
 int ans = INF;
 REP(i, C){
   REP(j, C){
     REP(k, C){
       if(i==j || j==k || k==i) continue;
       int d = 0;
       REP(l, C){
         d+= D[l][i]*cnt[0][l] + D[l][j]*cnt[1][l] + D[l][k]*cnt[2][l];
       }
       ans = min(ans, d);
     }
   }
 }
 cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1280
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main
{
	public static void main(String[] args)
	{
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		MyScanner in = new MyScanner(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		Solver solver = new C();
		solver.solve(1, in, out);
		out.close();
	}
	
	static class C implements Solver
	{
		long mod = (long) 1e9 + 7;

		public void solve(int testNumber, MyScanner in, PrintWriter out)
		{
			long n = in.nextLong();
			long ans = power(10, n) - 2 * power(9, n) + power(8, n);
			while( ans < 0 )
			{
				ans += mod;
			}
			while( ans >= mod )
			{
				ans -= mod;
			}
			out.println(ans);
		}
		
		long power(long x, long n)
		{
			if( n == 0 )
			{
				return 1;
			}

			if( n % 2 == 0 )
			{
				long X = (x * x) % mod;
				return power(X, n/2);
			}
			else
			{
				return (x * power(x, n-1)) % mod;
			}
		}
	}
	
	static class B implements Solver
	{
		public void solve(int testNumber, MyScanner in, PrintWriter out)
		{
			long a = in.nextInt();
			long b = in.nextInt();
			long c = in.nextInt();
			long d = in.nextInt();
			out.println(Math.max(Math.max(a*c, a*d), Math.max(b*c, b*d)));
		}
	}

	static class A implements Solver
	{
		public void solve(int testNumber, MyScanner in, PrintWriter out)
		{
			int x = in.nextInt();
			out.println(1 - x);
		}
	}

	static class UnionFind
	{
		int[] par;
		int[] n_nodes;
		int max = 1;
		
		public UnionFind(int n)
		{
			par = new int[n];
			n_nodes = new int[n];
			for( int i=0; i<n; i++ )
			{
				par[i] = i;
				n_nodes[i] = 1;
			}
		}
		
		int root(int x)
		{
			if( par[x] == x ) return x;
			return par[x] = root(par[x]);
		}
		
		void unite(int x, int y)
		{
			int rx = root(x);
			int ry = root(y);
			if( rx == ry ) return;
			par[rx] = ry;
			n_nodes[ry] += n_nodes[rx];
			max = Math.max(max, n_nodes[ry]);
		}
		
		boolean same(int x, int y)
		{
			int rx = root(x);
			int ry = root(y);
			return rx == ry;
		}
	}
	
	static class MyScanner
	{
		private BufferedReader in;
		private StringTokenizer st;
		
		public MyScanner(InputStream stream)
		{
			in = new BufferedReader(new InputStreamReader(stream));
		}
		
		public String next()
		{
			while( st == null || !st.hasMoreTokens() )
			{
				try
				{
					String rl = in.readLine();
					if( rl == null )
					{
						return null;
					}
					st = new StringTokenizer(rl);
				}
				catch( IOException e )
				{
					return null;
				}
			}
			return st.nextToken();
		}
		
		public int nextInt()
		{
			return Integer.parseInt(next());
		}
		
		public long nextLong()
		{
			return Long.parseLong(next());
		}
	}
	
	static interface Solver
	{
		public void solve(int testNumber, MyScanner in, PrintWriter out);
	}
}


Measured memory_bytes: 32796
/******************************************
* AUTHOR : RAJAGOPALAN *
* NICK : ARNO *
* INSTITUTION : VIT *
******************************************/
#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define alli(a, n, k) (a+k),(a+n+k)
#define FP(i, a, b, k) for(__typeof(a) i = a;i < b;i += k)
#define FS(i, a, b, k) for(__typeof(a) i = a;i > b;i -= k)
#define IT(it, a) for(__typeof(a.begin()) it = a.begin();it != a.end(); ++it)
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define eps 1e-6
#define pi 3.141592653589793
using namespace std;
using namespace __gnu_pbds;

template<class T> inline T gcd(T x, T y) { if (!y) return x; return gcd(y, x%y);}
typedef vector<int> VII;
typedef vector<ll> VLL;
typedef pair<int, int> PII;
typedef vector< pair<int, int> > VPII;
typedef vector< pair<int, PII > > VPPI;
const int MOD = 1e9 + 7;
const int INF = 1e9;

inline ll modulo(ll a, ll m)
{
    return (a % m + m) % m;
}

inline ll modInverse(ll a, ll m)
{
    assert(__gcd(a, m) == 1);
    ll m0 = m;
    ll y = 0, x = 1;

    if (m == 1)
        return 0;

    while (a > 1)
    {
        ll q = a / m;
        ll t = m;

        m = a % m, a = t;
        t = y;

        y = x - q * y;
        x = t;
    }

    if (x < 0)
        x += m0;

    return x;
}

inline ll modPow(ll x, ll y, ll m)
{ //x^y % m
    if (y == 0)
        return 1LL;
    else if (y == 1)
        return x;
    else
    {
        ll ans = modPow(x, y / 2, m) % m;
        if (y & 1)
        {
            return (((ans * ans) % m) * x) % m;
        }
        else
        {
            return (ans * ans) % m;
        }
    }
}

int main(int argc, char* argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    VII arr(n);
    ll sum=0;
    for(auto &x:arr){cin>>x;sum+=x;}
    int m;
    cin>>m;
    VPII st(m);
    for(auto &x:st)cin>>x.first>>x.second;
    for(auto gg:st)
    {
        sum-=arr[gg.first-1];
        sum+=gg.second;
        cout<<sum<<endl;
        sum-=gg.second;
        sum+=arr[gg.first-1];
    }


    return 0;
}

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

#define f(i,a,b) for( ll  i = a; i < b ; i++ ) 
#define af(i,a,b) for( ll i = a; i >= b ; i--)
#define rep(i,a,b,k) for(ll i = a; i < b ; i+= k )
#define arep(i,a,b,k) for( ll i = a; i >= b ; i-= k)
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define sz(a) (ll) a.size()
#define all(a) a.begin(), a.end()
#define sor(a) sort( a.begin(), a.end() )
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL)
#define inter ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)

// policy-based



using namespace std;


typedef long long ll; // int or long long
typedef long double ld;
typedef pair<ll,ll> ii ;
typedef vector<ll>  vi ;
typedef vector<ii> vii ;



 
const ll MAX = 2e5+10;
const ll inf = 1e15;
const ll mod = 1e9+7;

ll a[MAX];



int main(){
	fastio;
	ll n;
	cin >> n;
	f(i,0,n) cin >> a[i];
	ll ans = 0;
	f(i,0,n){
		f(j,i+1,n){
			f(k,j+1,n){
				if(a[i] == a[j] || a[j]==a[k] || a[i] == a[k]) continue;
				if( a[k] < a[i] + a[j]  && a[i] < a[j] + a[k] && a[j] < a[i]+a[k] ) ans++;
		//		cout << a[k] <<" " << a[i] + a[j]<<endl;
			}
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 3688
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <tuple>
#include <cassert>
#include <functional>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
const int INF = 1<<29;
#define LNF __LONG_LONG_MAX__
const ll MOD = 1000000007;
const int MAX = 200000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
// 法mでのaの逆元を計算
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
//最大公約数
int gcd(int x, int y) { return (x % y)? gcd(y, x % y): y; }
//最小公倍数
int lcm(int x, int y) { return x / gcd(x, y) * y; }
// nが大きく,kが10^7程度の時の二項係数
long long com[200005];
void combination(long long n,long long k){
    com[0] = 1;
    for(int i=1;i<=k;i++){
        com[i] = (com[i-1]*(n-i+1)%MOD)*modinv(i,MOD)%MOD;
    }
}

int main(){
    ll X;
    cin >> X;
    ll n = 100;
    ll cnt=0;
    while(n<X){
        cnt++;
        n = (ll)(n*1.01);
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 3600
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

ans = 0
for i in range(N):
    ans += B[i]

for j in range(N):
    if j >= 1:
        if A[j] == A[j - 1] + 1:
            tmp = A[j] - 2
            ans += C[tmp]

print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll t,n,m,i,j,k,sum;
    cin>>n>>m;
    if(m>=n)
        cout<<"unsafe";
    else
        cout<<"safe";
}


Measured memory_bytes: 3636
using System;

namespace ABC131
{
    class B
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            int N = int.Parse(input[0]);
            int L = int.Parse(input[1]);

            int[] aji = new int[N];

            for (int i = 0; i < N; i++)
            {
                aji[i] = L + i;
            }

            if (0 <= L) { aji[0] = 0; }
            if (L < 0)
            {
                if (Math.Abs(L) >= Math.Abs(N))
                {
                    aji[N - 1] = 0;
                }
            }

            int res = 0;
            foreach (var k in aji)
            {
                res += k;
            }
            Console.WriteLine(res);
        }
    }
}


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

int main()
{
  int n;
  cin>>n;
  vector<int> v(n),dp(n);
  for(int &i:v)cin>>i;
  
  dp[0]=0;
  dp[1]=abs(v[1]-v[0]);
  
  for(int i=2;i<n;i++)
  {
    dp[i] = min(abs(v[i]-v[i-1])+dp[i-1],abs(v[i]-v[i-2])+dp[i-2]);
    
  }

  //for(int i:dp)cout<<i<<" ";
  
  cout<<dp[n-1]<<endl;
}

Measured memory_bytes: 1024
# -*- coding: utf-8 -*-

## Library

import sys
from fractions import gcd
import math
from math import ceil,floor
import collections
from collections import Counter
import itertools
import copy

## input

# N=int(input())
# A,B,C,D=map(int, input().split())
# S = input()
# yoko = list(map(int, input().split()))
# tate = [int(input()) for _ in range(N)]
# N, M = map(int,input().split()) 
#    P = [list(map(int,input().split())) for i in range(M)]
#    S = []
#    for _ in range(N):
#        S.append(list(input()))

N = int(input())
S = input()

ans = 0

for i in range(1,N):
    Cfirst = collections.Counter(S[:i])
    Cend = collections.Counter(S[i:])
    ans = max(ans, len(Cfirst.keys() & Cend.keys()))

print(ans)

Measured memory_bytes: 77652
#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
#define FLASH cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
#define FILEIO freopen("/home/aman/Desktop/Kachda/input.txt", "r", stdin); //freopen("/home/aman/Desktop/Kachda/output.txt", "w", stdout);
using namespace std;

int x, y, a, b, c;
priority_queue <int> q;
signed main()
{
	//FILEIO
    FLASH
	
	cin>>x>>y>>a>>b>>c;
	vector <int> v;
	int ans = 0;
	for(int i = 0; i < a; i++){
		int t;
		cin>>t;
		v.push_back(t);
	}
	sort(v.begin(), v.end());
	reverse(v.begin(), v.end());

	for(int i = 0; i < x; i++){
		q.push(-v[i]);
		ans += v[i];
	}
	v.clear();

	for(int i = 0; i < b; i++){
		int t;
		cin>>t;
		v.push_back(t);
	}
	sort(v.begin(), v.end());
	reverse(v.begin(), v.end());

	for(int i = 0; i < y; i++){
		q.push(-v[i]);
		ans += v[i];
	}
	v.clear();	
	for(int i = 0; i < c; i++){
		int t;
		cin>>t;
		v.push_back(t);
	}
	sort(v.begin(), v.end());
	reverse(v.begin(), v.end());
	for(int i = 0; i < (int) v.size(); i++){
		if(-q.top()	< v[i]){
			ans +=  v[i] + q.top();
			q.pop();
		}
		if(q.empty())
			break;
	}

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

Measured memory_bytes: 3188
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split())) + [0]

ans = 0

for i in range(N):
    k = A[i] - 1
    ans += B[k]

for i in range(N - 1):
    k = A[i] - 1
    if A[i] + 1 == A[i + 1]:
        ans += C[k]

print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>

using namespace std;

int main(){
  int x1,y1,x2,y2;
  cin >> x1 >> y1 >> x2 >> y2;
  int a=x2-x1,b=y2-y1;

  cout << x2-b << " " << y2+a << " " << x1-b << " " << y1+a << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
 int a[105];
 queue<int>s;
int main()
{
      int n,sum=0;
      cin>>n;
      for(int i=0;i<n;i++)
            cin>>a[i];
            int flag=0;
            a[n]=0;
  int maxn=a[0];
          int i=1;
   while(i<=n)
   {
      if(a[i]>=maxn)
        {
            maxn=a[i];
            i++;
        }
      else
      {
           if(a[i]==0)
           {
               sum+=maxn;
               maxn=a[i+1];
               i++;
           }
           else
           {
               sum+=maxn-a[i];
               int s=a[i];
               i++;
               while(a[i]<=s&&i<=n)
               {
                    sum+=s-a[i];
                     s=a[i];
                     i++;
               }
               maxn=a[i];
           }

      }
   }
   printf("%d\n",sum);



    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

typedef long long ll;
typedef uint64_t ull;
typedef pair<int, int> P;
constexpr double PI = 3.1415926535897932;   // acos(-1)
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)

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

    int n, q;
    string s;
    cin >> n >> q >> s;
    vector<int> sum(n + 1, 0);
    for(int i = 0; i + 1 < n; ++i){
        if(s[i] == 'A' && s[i + 1] == 'C')  sum[i + 1] = 1;
    }
    for(int i = 0; i < n; ++i)  sum[i + 1] += sum[i];
    for(int i = 0; i < q; ++i){
        int l, r;
        cin >> l >> r;
        --l, --r;
        int ans = sum[r] - sum[l];
        cout << ans << '\n';
    }
}

Measured memory_bytes: 1488
#include <iostream>

using namespace std;

int N, T;
int t[200000];

int main(){

    cin >> N >> T;

    for(int i = 0; i < N; i++)
        cin >> t[i];

    int ans = T;

    for (int i = 0; i < N - 1; i++){

        int diff = t[i + 1] - t[i];
        
        if (diff < T)
            ans += diff;
        else
            ans += T;
    }
    
    cout << ans << '\n';

}



Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int INF = 1<<30; 
const int MOD = 1e9 + 7;
const int dy[] = {1, 0, -1, 0};
const int dx[] = {0, 1, 0, -1};
const int MAX_N = 1e6;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, d, x; cin >> n >> d >> x;
    int p[d + 1][n + 1];
    for(int i = 0; i < d; i++) 
    {
        for(int j = 0; j < n; j++) cin >> p[i][j];
    }
    int dp[MAX_N + 1];
    int now = x;
    for(int day = 0; day < d - 1; day++)
    {
        for(int money = 0; money <= now; money++) dp[money] = money;
        int tmp = x;
        for(int num = 0; num < n; num++)
        {
            for(int money = 0; money <= now; money++)
            {
                if(money - p[day][num] < 0) continue;
                dp[money] = max(dp[money], dp[money - p[day][num]] + p[day + 1][num]);
                tmp = max(dp[money], tmp);
            }
        }
        now = tmp;
    }
    cout << now << endl;
    return 0;
}




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

using namespace std;
typedef long long ll;

#define rep(i, N) for (int i = 0; i < (int)N; i++)
const ll MOD = pow(10,9)+7;
const ll LLINF = pow(2,61)-1;
const int INF = pow(2,30)-1;


int main() {
  int X, Y; cin >> X >> Y;
  int result = max(0,4-X)*100000 + max(0,4-Y)*100000;
  if (result==600000) result = 1000000;
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 256
module Main where

import qualified Data.List as DL
import qualified Control.Monad as CM

readInt :: String -> Int
readInt = read

solveB :: IO ()
solveB = do
  [n, m] <- fmap read . words <$> getLine
  set <- foldl1 DL.intersect <$> CM.replicateM n (fmap readInt . tail . words <$> getLine)
  print $ length set
  
main = solveB

Measured memory_bytes: 1148
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N= 1e5 + 5;
const ll mod=1e9 + 7;

int main(){
    ios_base:: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    ll r;
    cin>>r;
    cout<<r*r;
}



Measured memory_bytes: 764
import java.util.ArrayList;
import java.util.Scanner;


public class Main {

        public static void main(String[] args)
    {
        Scanner in=new Scanner(System.in);
        int N = in.nextInt();
        int count1 =0, count2 =0, count3 = 0, count4 =0;
        ArrayList<String> m= new ArrayList<>();
        for (int i = 0; i < N; i++) {
            String s = in.next();
            m.add(s);
        }
        for (String s : m) {
            switch (s) {
                case "AC":
                    count1++;
                    break;
                case "WA":
                    count2++;
                    break;
                case "TLE":
                    count3++;
                    break;
                case "RE":
                    count4++;
                    break;
            }
        }
        System.out.println("AC x " + count1);
        System.out.println("WA x " + count2);
        System.out.println("TLE x " + count3);
        System.out.println("RE x " + count4);
    }
}

Measured memory_bytes: 65720
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		long N = long.Parse(Console.ReadLine());
		long[,] A = new long[N,2];
		for(var i=0;i<N;i++){
			string[] str = Console.ReadLine().Split();
			A[i,0] = long.Parse(str[0]);
			A[i,1] = long.Parse(str[1]);
		}
		long c = (Math.Abs(A[0,0])+Math.Abs(A[0,1])) % 2;
		bool f = true;
		for(var i=1;i<N;i++){
			if((Math.Abs(A[i,0])+Math.Abs(A[i,1])) % 2 != c){
				f = false;
				break;
			}
		}
		if(f == false){
			Console.WriteLine("-1");
		} else {
			long[] M = new long[33];
			long ms = 32;
			if(c == 0){
				ms = 33;
				M[32] = 1;
			}
			long t = 1;
			for(var i=0;i<32;i++){
				M[31-i] = t;
				t *= 2;
			}
			Console.WriteLine(ms);
			string str2 = "" + M[0];
			for(var i=1;i<ms;i++){
				str2 += " " + M[i];
			}
			Console.WriteLine(str2);
			for(var i=0;i<N;i++){
				string ans = "";
				long ax = 0;
				long ay = 0;
				for(var j=0;j<ms;j++){
					if(Math.Abs(A[i,0]-ax) > Math.Abs(A[i,1]-ay)){
						if(A[i,0] > ax){
							ax += M[j];
							ans += "R";
						} else {
							ax -= M[j];
							ans += "L";
						}
					} else {
						if(A[i,1] > ay){
							ay += M[j];
							ans += "U";
						} else {
							ay -= M[j];
							ans += "D";
						}
					}
				}
				Console.WriteLine(ans);
			}
		}
	}
}

Measured memory_bytes: 15292
#include<bits/stdc++.h>
using namespace std;
int main(){
int64_t N,K;
  cin>>N>>K;
  int64_t ans=0;
  for(int64_t k=K;k<=N+1;k++){
  int64_t x=((k*(N-k+1)+1)%1000000007);
    ans+=x;
  } int64_t X=(ans%1000000007);
  cout<<X<<endl;
   return 0;
}

Measured memory_bytes: 3636
package main

import (
	"fmt"
	"math"
)

func main() {
	var N, P int
	fmt.Scanf("%d%d", &N, &P)
	ans := 1
	A := int(math.Pow(float64(P), 1/float64(N)))
	if N == 1 {
		fmt.Printf("%d\n", P)
		return
	}
	for ord, i := 0, 2; ; {
		if P%i != 0 {
			if P == 1 || i > A {
				break
			}
			ord = 0
			i += 1 + i%2
		} else {
			ord++
			if ord%N == 0 {
				ans *= i
			}
			P /= i
		}
	}
	fmt.Printf("%d\n", ans)
}


Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <iomanip>
#include <set>
using namespace std;
typedef long long int ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl

const int INF = 1001001001;
const int mod = 1000000007;
#define PI 3.14159265359;

void P(int x) {cout << x << endl;}
void P(long x) {cout << x << endl;}
void P(double x) {cout << x << endl;}
void P(ll x) {cout << x << endl;}
void P(string x) {cout << x << endl;}
void P(char x) {cout << x << endl;}

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

int main() {
  int n;
  string s;
  cin >> n >> s;
  int ans = 0;
  for (int i = 1; i < s.size(); i++) {
    set<char> se1, se2;
    rep (j, i) {
      se1.insert(s[j]);
    }
    for (int j = i; j < s.size(); j++) {
      se2.insert(s[j]);
    }
    int count = 0;
    for (auto itr = se1.begin(); itr != se1.end(); itr++) {
      if (se2.find(*itr) != se2.end()) count++;
    }
    ans = max(count, ans);
  }
  P(ans);
  return 0;
}



Measured memory_bytes: 256
import sys
input = sys.stdin.buffer.readline

def main():
    x = int(input())

    b = 1
    p = 2

    a = []

    for i in range(int(x ** 0.5) + 1):
        for j in range(int(x ** 0.5) + 1):
            if (b+i) ** (p+j) <= x:
                a.append((b+i) ** (p+j))

    print(max(a))

if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>

using namespace std;

typedef long long LL;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define Fst first
#define Snd second
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))

const int ST_MAX = (1 << 20);

template <class T> class ST{
	T x[ST_MAX * 2];
	
	T eval(T a , T b){			//評価
		return a > b ? a : b;
	}
	
	void ren(int a){			//更新
		x[a] = eval(x[2 * a] , x[2 * a + 1]);
		if(a > 0) ren(a / 2);
	}
	
	T read_ST(int a , int b , int e , int s , int f){		//値の取得
		if(e <= s || f <= b) return 0;
		if(s <= b && e <= f) return x[a];
		return eval(read_ST(2 * a , b , (b + e) / 2 , s , f) , read_ST(2 * a + 1 , (b + e) / 2 , e , s , f));
	}
	
public:
	
	void put(int a , T b){	//更新の開始
		x[a + ST_MAX] = b;
		ren((a + ST_MAX) / 2);
	}
	
	T get(int s , int f){	//値の取得の開始
		return read_ST(1 , 0 , ST_MAX , s , f);
	}
};

ST<int> st;
int N;
int a;
LL dp[200010];
LL g[200010];

int main(){
	scanf("%d" , &N);
	for(int i = 1 ; i <= N ; ++i){
		scanf("%d" , &a);
		int y = st.get(0 , a);
		g[i] = g[y] + (LL)a * (i - y);
		dp[i] = g[i] + dp[i - 1];
		st.put(a , i);
	}
	printf("%lld\n" , dp[N]);
	return 0;
}


Measured memory_bytes: 4864
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;
using static System.Console;
using static System.Math;
class Z { static void Main() => new K(); }
class K
{
	int F => int.Parse(Str);
	long FL => long.Parse(Str);
	int[] G => Strs.Select(int.Parse).ToArray();
	decimal[] GD => Strs.Select(decimal.Parse).ToArray();
	long[] GL => Strs.Select(long.Parse).ToArray();
	string Str => ReadLine();
	string[] Strs => Str.Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries);
	static T[] ConstantArray<T>(int n, T val) { var a = new T[n]; for (var i = 0; i < n; i++) a[i] = val; return a; }
	static T[] MakeArray<T>(int n, Func<int, T> f) { var a = new T[n]; for (var i = 0; i < n; i++) a[i] = f(i); return a; }
	const int MOD = 1000000007;
	public K()
	{
		SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
		WriteLine(Solve());
		Out.Flush();
	}
	long Solve()
	{
		var I = GL;
		long A = I[0], B = I[1];
		if (A == B) return A;
		if (A == 0) A++;
		var ans = 0L;
		for (var i = 0; i < 50; i++) if ((Calc(B, i) - Calc(A - 1, i)) % 2 == 1) ans |= 1L << i;
		return ans;
	}
	// [0,n] の整数のうち k ビット目が 1 のものの個数
	long Calc(long n, int k)
	{
		if (k == 0) return (n + 1) / 2;
		var m = 1L << k;
		if (n < m) return 0;
		if ((n & m) == 0) return Calc(n >> k, 0) << k;
		return (n & (m - 1)) + 1 + Calc(n ^ m, k);
	}
}


Measured memory_bytes: 13268
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
char s[100005];

LL L;
int n, l;
struct trie{
    trie *nt[2];
    bool ok;
    trie(){
        nt[0] = nt[1] = NULL;
        ok = 0;
    }
};

trie *root = new trie();

void add(trie *cur, int i){
    if(i == l+1){
        cur->ok = 1;
    }
    else{
        int c = s[i]-'0';
        if(cur->nt[c] == NULL) cur->nt[c] = new trie();
        add(cur->nt[c], i+1);
    }
}
LL ans = 0;
void dfs(trie *cur, int j){
    if(cur->ok) return;
    for(int i=0;i<2;i++){
        if(cur->nt[i] == NULL){
            LL v = L+1-j, mul = 1;
            for(int j=0;j<60;j++){
                if((v>>j)&1) break;
                mul *= 2;
            }

            ans ^= mul;
        }
        else dfs(cur->nt[i], j+1);
    }
}

int main(){
    scanf("%d%lld", &n, &L);   
    for(int i=1;i<=n;i++){
        scanf("%s", s+1);
        l = strlen(s+1);
        add(root, 1);
    }
    dfs(root, 1);
    if(ans == 0) printf("Bob\n");
    else printf("Alice\n");
}

Measured memory_bytes: 8192
#include<iostream>
using namespace std;
long N;
int cnt;
main()
{
	cin>>N;
	for(long i=2;i*i<=N;i++)
	{
		if(N%i==0)
		{
			int c=0;
			while(N%i==0)
			{
				N/=i;
				c++;
			}
			int z=1;
			while(c>=z)
			{
				c-=z++;
				cnt++;
			}
		}
	}
	if(N>1)cnt++;
	cout<<cnt<<endl;
}


Measured memory_bytes: 3624
#https://atcoder.jp/contests/diverta2019-2/submissions/11229318
n = int(input())
t = [tuple(map(int, input().split())) for _ in range(n)]
s = set(t)
cnt = 0
for i in range(n-1):
  for j in range(i+1,n):
    u,v = t[i]
    x,y = t[j]
    p = u-x; q = v-y
    c = sum((x-p, y-q) in s for x,y in t)
    if cnt < c: cnt = c
print(n-cnt)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
 #include <ext/pb_ds/tree_policy.hpp>
 #include <ext/pb_ds/assoc_container.hpp>
 #include<chrono>
 using namespace std;
 using namespace std::chrono;      
 using namespace __gnu_pbds; 
 #define fastio     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
 #define fi         first
 #define se         second
#define int         long long 
 #define pb         push_back
 #define emp        emplace_back
 #define vv(x)      vector<x>
 #define mp(x,y)    map<x,y>
 #define dq(x)      deque<x>
 #define pql(x)     priority_queue<x>
 #define pqs(x)     priority_queue<x,vv(x),greater<x> >
 #define M          1000000007
 #define forf(i,a,b) for(int i=a;i<b;i++)
 #define it(x)      x::iterator
 #define ll         long long 
 #define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
 #define time__(d)  for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false); debug("%s time : %.4fs", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
 #define vii        vector<int>
 #define big        3e18
 #define sm         -2e9
 #define mkr        make_pair
 #define vpi        vector<pair<int,int> >
 #define pii        pair<int,int>
 #define rng        500005
 #define sz(x)      (int)x.size()
 #define rv(x)      reverse(x.begin(),x.end())
 #define out(x)     cout<<x.fi<<" "<<x.se<<endl;

//#define ordered_set tree<pii, null_type,less<pii>, rb_tree_tag,tree_order_statistics_node_update> 
  
void pr_init()
{
   
    #ifndef ONLINE_JUDGE
    freopen("gin.txt", "r", stdin);
    freopen("gout.txt", "w", stdout);
   
    #endif
}



void solve()
{
 
 int n;
 cin >> n ;

 int an = (int)ceil(n/1000.0)*1000-n;
 cout<<an;
}


int32_t main()
{
  pr_init();
  fastio;
  
  auto start = high_resolution_clock::now(); 
 
  solve();
  auto stop = high_resolution_clock::now();
  auto duration = duration_cast<microseconds>(stop - start); 
   // cout << "Time taken by function: "
   //       << duration.count() << " microseconds" << endl; 

 }
      
      

Measured memory_bytes: 3760
/*suri_kumkaran*/

#include <bits/stdc++.h>

using namespace std;

#define UB upper_bound
#define LB lower_bound
#define BS binary_search
#define MP make_pair
#define EB emplace_back
#define endl "\n"
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
#define F first
#define S second
#define ALL(a) (a).begin(),(a).end()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define int long long

typedef long long int64;
typedef vector<int> VI64;
typedef vector<pair<int,int>> VII64;
typedef vector<string> VS;
typedef vector<vector<int>> VVI;

int64 ME(int64 a,int64 b,int64 m)
{
    int64 mul=a,ans=1;
    while(b)
    {
      if(b&1)
      {
        ans*=mul;
        ans%=m;
      }
      mul*=mul;
      mul%=m;
      b/=2;
    }
    return ans%m;
}


int32_t main()
{
	IOS;
	int T=1;
	//cin>>T;
	while(T--)
	{	
		int n,k,i;
		cin>>n>>k;
		int ans=0;
		for(i=k;i<=n+1;i++)
		{
			int mn=(((i-1)*(i))/2)%MOD;
			int mx=(((n)*(n+1))/2)%MOD - (((n-i)*(n-i+1))/2)%MOD   + MOD;
			mx%=MOD;
			ans+=(mx-mn+1+MOD)%MOD;
			ans%=MOD;
		}
		cout<<ans;
	}

	return 0;
}

Measured memory_bytes: 3648
N = int(input())
A = list(map(int, input().split()))
TorF = True

for i in range(N):
  if A[i]%2==0 and not (A[i]%3==0 or A[i]%5==0):
    TorF = False
    break

if TorF == True:
  print("APPROVED")
else:
  print("DENIED")

Measured memory_bytes: 3060
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <queue>
#include <map>
#include <fstream>
#include <array>
#include <utility>
#include <functional>
#include <stack>
#include <math.h>

using namespace std;
typedef long long Int;
#define REP(i , x) for(Int i = 0 ; i < x ; ++i)
typedef pair<int, int> P;


int main()
{
	int a, b;

	double x = 0; 
	double y = 0;
	int radius = 90;


	while (scanf("%d,%d", &a, &b), a||b){
		y += a*sin(radius*M_PI/180);
		x += a*cos(radius*M_PI/180);
		radius -= b;
	}

	cout << (int)x << endl << (int)y << endl;                                                        
	return 0;
}

Measured memory_bytes: 1204
import sys
sys.setrecursionlimit(10**8)

S = input()
T = input()

N,M = len(S),len(T)

dp = [[0]*(M+1) for i in range(N+1)]

for i,s in enumerate(S):
    for j,t in enumerate(T):
        if s==t:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

ans = ''
def rec(i,j):
    if i==0 or j==0: return
    if S[i-1] == T[j-1]:
        global ans
        ans += S[i-1]
        rec(i-1,j-1)
    elif dp[i-1][j] >= dp[i][j-1]:
        rec(i-1,j)
    else:
        rec(i,j-1)
rec(N,M)
print(ans[::-1])

Measured memory_bytes: 118364
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll mod2 = 998244353;
const ll INF = 1e18;
const long double EPS = 1e-10;

int main() {
  int x;
  cin >> x;
  
  cout << (x < 1200 ? "ABC" : "ARC") << endl;


  
  return 0;
}

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




int main() {
	
	int n,m;
	cin>>n>>m;
	
	
	if(n==m){
	    std::cout << "Yes" << std::endl;
	}
	else
	std::cout << "No" << std::endl;
	
	
	return 0;
}


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

#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define lfs <<fixed<<setprecision(10)<<
#define test cout<<"test"<<endl;
#define fi first
#define se second
#define MP make_pair
#define rep(i,n,m) for(ll i = n; i < (ll)(m); i++)
#define rrep(i,n,m) for(ll i = n - 1; i >= (ll)(m); i--)
typedef long long ll;
typedef long double ld;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const ll INF = 1e18;
using P = pair<ll, ll>;
template<typename T>
void chmin(T &a,T b){if(a>b)a=b;}
template<typename T>
void chmax(T &a,T b){if(a<b)a=b;}
void pmod(ll &a,ll b){a=(a+b)%MOD;}
void pmod(ll &a,ll b,ll c){a=(b+c)%MOD;}
void qmod(ll &a,ll b){a=(a*b)%MOD;}
void qmod(ll &a,ll b,ll c){a=(b*c)%MOD;}
ll median(ll a,ll b, ll c){return a+b+c-max({a,b,c})-min({a,b,c});}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
template<typename T1,typename T2>
void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;}  
template<typename T>
void debug(vector<vector<T>>v,ll h,ll w){for(ll i=0;i<h;i++)
{cout<<v[i][0];for(ll j=1;j<w;j++)cout spa v[i][j];cout<<endl;}};
void debug(vector<string>v,ll h,ll w){for(ll i=0;i<h;i++)
{for(ll j=0;j<w;j++)cout<<v[i][j];cout<<endl;}};
template<typename T>
void debug(vector<T>v,ll n){cout<<v[0];
for(ll i=1;i<n;i++)cout spa v[i];cout<<endl;};
template<typename T>
vector<vector<T>>vec(ll x, ll y, T w){
  vector<vector<T>>v(x,vector<T>(y,w));return v;}
ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;}
template<typename T>
void emp(map<T,ll>&m, T x){m.emplace(x,0).first->second++;}

int main(){
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);
  ll res=0,res1=INF,res2=-INF,buf=0;
  bool judge = true;
  string s;cin>>s;
  cout<<count(ALL(s),'1')<<endl;
  return 0;
}

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

using namespace std;
using ll = long long;

const vector<vector<int>> dir4 = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
const vector<vector<int>> dir8 = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}, {1, 1}, {-1, 1}, {1, -1}, {-1, -1}};

int main()
{
    int h = 100, w = 100;
    int a, b; cin >> a >> b;
    a--, b--;
    vector<vector<int>> grd(h, vector<int>(w));
    for(int i = 0; i < h / 2; i++) {
        for(int j = 0; j < w; j++)grd[i][j] = 1;
    }
    
    for(int i = 1; i < h / 2 - 1; i++) {
        for(int j = 1; j < w - 1 && b; j++) {
            bool res = 1;
            for(auto d : dir8)if(grd[i + d[0]][j + d[1]] == 0)res = false;
            if(res)grd[i][j] = 0;
            if(res)b--;
        }
    }

    cerr << "27" << endl;

    for(int i = h / 2 + 2; i < h - 1; i++) {
        for(int j = 1; j < w - 1 && a; j++) {
            bool res = 1;
            for(auto d : dir8)if(grd[i + d[0]][j + d[1]] == 1)res = false;
            if(res)grd[i][j] = 1;
            if(res)a--;
        }
    }

    cerr << "35" << endl;

    cout << h << " " << w << endl;
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            cout << (grd[i][j] ? '.' : '#');
        }
        cout << endl;
    }

}

Measured memory_bytes: 256
from collections import defaultdict as dd
N = int(input())
Es = dd(dict)
for _ in range(N-1):
    a, b = map(int, input().split())
    Es[a-1][b-1] = Es[b-1][a-1] = 1

# もっとも長いパスを見つける
q = [0]
visited = [False] * N
last = None
while q:
    nq = []
    for node in q:
        last = node
        visited[node] = True
        for to in Es[node]:
            if visited[to]:
                continue
            nq.append(to)
    q = nq

q = [last]
visited = [False] * N
n = 0
while q:
    n += 1
    nq = []
    for node in q:
        visited[node] = True
        for to in Es[node]:
            if visited[to]:
                continue
            nq.append(to)
    q = nq

if n % 3 == 2:
    print('Second')
else:
    print('First')


Measured memory_bytes: 100800
N, M = map(int, input().split())

# 最初は全て繋がっているが、1本ずつ崩落していく。
# uniteし続けて、最終的に親が違うものは分離しているとみなせる？


parents = None


def root(x):
    if parents[x] < 0:
        return x
    if parents[x] == x:
        return x
    parents[x] = root(parents[x])
    return parents[x]


count = 0


def unit(x, y):
    root_x = root(x)
    root_y = root(y)
    if root_x == root_y:
        return

    if parents[root_x] > parents[root_y]:
        root_x, root_y = root_y, root_x
    parents[root_x] += parents[root_y]
    parents[root_y] = root_x


def same(x, y):
    root_x = root(x)
    root_y = root(y)
    return (root_x == root_y)


def size(x):
    return -parents[root(x)]


es = []
for i in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    es.append((a, b))


parents = [-1] * N
ans = [0 for _ in range(M + 1)]
ans[M] = N * (N - 1) // 2
for i, e in enumerate(es[::-1]):
    # print('===========')
    a, b = e
    if root(a) != root(b):
        # print(size(a), size(b))
        x, y = size(a), size(b)
    else:
        x, y = 0, 0
    unit(a, b)
    ans[M - 1 - i] = ans[M - i] - (x * y)
    # print(parents)


# print(ans)
for num in ans[1:]:
    print(num)


Measured memory_bytes: 100952
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int MOD = 998244353;

int main() {
  int n;
  string x;
  cin >> n >> x;

  vector<int> c;
  for (int i = 1; i <= n; i++) {
    if (n % i == 0 && n / i % 2 == 1) c.push_back(i);
  }

  vector<vector<vector<ll>>> dp(n + 1, vector<vector<ll>>(2, vector<ll>(c.size())));
  fill(dp[0][0].begin(), dp[0][0].end(), 1);
  for (int i = 0; i < n; i++) {
    for (int less = 0; less < 2; less++) {
      for (int j = 0; j < c.size(); j++) {
        if (i < c[j]) {
          (dp[i + 1][less][j] += dp[i][less][j]) %= MOD;
          if (less || x[i] - '0' == 1) (dp[i + 1][true][j] += dp[i][less][j]) %= MOD;
        } else if (x[i - c[j]] - '0' != x[i] - '0') {
          (dp[i + 1][less][j] += dp[i][less][j]) %= MOD;
        } else if (less || x[i] - '0' == 1) {
          (dp[i + 1][true][j] += dp[i][less][j]) %= MOD;
        }
      }
    }
  }
  for (int less = 0; less < 2; less++) {
    for (int j = 0; j < c.size(); j++) {
      for (int k = j + 1; k < c.size(); k++) {
        if (c[k] % c[j] == 0 && c[k] / c[j] % 2 == 1) dp[n][less][k] = (MOD + dp[n][less][k] - dp[n][less][j]) % MOD;
      }
    }
  }

  // for (auto e : c) cerr << e << ' ';
  // cerr << endl;
  // for (int i = 0; i < n; i++) {
  //   cerr << i + 1 << endl;
  //   for (int less = 0; less < 2; less++) {
  //     for (int j = 0; j < c.size(); j++) {
  //       cerr << less << ' ' << c[j] << ' ' << dp[i + 1][less][j] << endl;
  //     }
  //   }
  // }

  ll r = 0;
  for (int less = 0; less < 2; less++) {
    for (int j = 0; j < c.size(); j++) {
      r += dp[n][less][j] * (2 * c[j] % MOD) % MOD;
      r %= MOD;
    }
  }
  cout << r << endl;
}


Measured memory_bytes: 221060
from collections import deque


def dfs(field):
    q = deque([(0, 0, 1)])
    visited = [[False] * w for _ in range(h)]
    while q:
        i, j, d = q.popleft()
        if i == h - 1 and j == w - 1:
            return d
        if visited[i][j]:
            continue
        visited[i][j] = True
        if i > 0 and field[i - 1][j] == '.':
            q.append((i - 1, j, d + 1))
        if i < h - 1 and field[i + 1][j] == '.':
            q.append((i + 1, j, d + 1))
        if j > 0 and field[i][j - 1] == '.':
            q.append((i, j - 1, d + 1))
        if j < w - 1 and field[i][j + 1] == '.':
            q.append((i, j + 1, d + 1))
    else:
        return -1


h, w = map(int, input().split())
field = [input() for _ in range(h)]
init_black = sum(r.count('#') for r in field)
res = dfs(field)
if res == -1:
    print(-1)
else:
    print(h * w - res - init_black)


Measured memory_bytes: 3444
import java.util.Scanner;

public class Main{
		
	public static void main(String args[]){
		  
	    Scanner sc = new Scanner(System.in);
	    
	    int N = sc.nextInt();
	    int T = sc.nextInt();
	    int A = sc.nextInt();
	    
	    int h;
	    double min = 114514;
	    int ans = 0;
	    for(int i = 1; i <= N; i++) {
	    	h = sc.nextInt();
	    	
	    	double tmp = T-h*0.006;
	    	double dis = Math.abs(A-tmp);
	    	
	    	if(min > dis) {
	    		min = dis;
	    		ans = i;
	    	}
	    }
	    
	    System.out.println(ans);
	    
	    
	}
	
}

Measured memory_bytes: 22228
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
using namespace std;

long long dfs(string s[25], int n, int y, int x) {
    //cout << y << ' ' << x << endl;;
    if(isdigit(s[y][x])){
        return s[y][x] - '0';
    }else if(s[y][x] == '.'){
        assert(0);
    }else{
        long long res;
        //show(s[y][x])
        if(s[y][x] == '+'){
            res = 0;
            range(i,y + 1,n){
                //cout << i << ' ' << x + 1 << endl;
                if(x + 1 >= s[i].size()) break;
                if(s[i][x + 1] == '.') continue;
                res += dfs(s,n,i,x + 1);
            }
        }else{
            res = 1;
            range(i,y + 1,n){
                if(x + 1 >= s[i].size()) break;
                if(s[i][x + 1] == '.') continue;
                res *= dfs(s,n,i,x + 1);
            }
        }
        //show(res)
        return res;
    }
    assert(0);
    return 0;
}

int main(){
    int n;
    while(cin >> n,n){
        string s[25];
        rep(i,n) cin >> s[i];
        cout << dfs(s,n,0,0) << endl;
    }
}

Measured memory_bytes: 3072
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1ll<<60)
typedef pair<int, int> P;
typedef pair<int, P> E;
#define MOD (1000000007ll)
#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	b += MOD;
	a += b;
	a %= MOD;
}

int n;
string s,d="dreamer",e="eraser";
bool memo[123456],done[123456];

bool dp(int i){
	int j,p=0;
	if(done[i]){
		return memo[i];
	}
	done[i] = true;
	memo[i] = false;
	if(i==n){
		memo[i] = true;
		return memo[i];
	}
	if(s[i]!='d' && s[i]!='e'){
		return memo[i];
	}
	if(s[i]=='d'){
		for(j=i; j<min(n,j+7); ++j){
			if(s[j]!=d[j-i]){
				break;
			}
			++p;
		}
		if(p==7){
			memo[i] = dp(i+5)|dp(i+7);
		}else if(p==5){
			memo[i] = dp(i+5);
		}
	}else{
		for(j=i; j<min(n,j+6); ++j){
			if(s[j]!=e[j-i]){
				break;
			}
			++p;
		}
		if(p==5 || p==6){
			memo[i] = dp(i+p);
		}else{
			memo[i] = false;
		}
	}
	return memo[i];
}

int main(void){
	fill(done,done+123456,false);
	cin >> s;
	n = s.l_ength();
	cout << ((dp(0)?"YES":"NO")) << endl;
	return 0;
}

Measured memory_bytes: 2048
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <string.h>

#define loop(lp) for(int lp2 = 0; lp2 < lp; lp2 ++)
#define ascent(i, a, b) for(int i = a; i < b; i ++)

#define pb push_back

using namespace std;

int dp[1010][10010];

int main() {
  int w_max, count = 0;
  while(cin >> w_max, w_max) {
    count ++;
    int n;
    cin >> n;
    
    memset(dp, 0, sizeof(dp));

    int v, w;
    pair<int, int> w_sum;
    w_sum = make_pair(0, 0);

    ascent(i, 1, n+1) {
      scanf("%d,%d", &v, &w);

      ascent(j, 1, w_max+1) {
	if(w <= j) {
	  if(dp[i-1][j] < dp[i-1][j-w] + v) {
	    dp[i][j] = dp[i-1][j-w] + v;

	    if(w_sum.first < dp[i][j] || w_sum.first == dp[i][j] && j < w_sum.second) {
	      w_sum = make_pair(dp[i][j], j); 

	      //cout << "i = " << i << " " << "wsum = " << w_sum.second << endl;
	    }
	  }
	  else {
	    dp[i][j] = dp[i-1][j];
	  }
	}
	else {
	  dp[i][j] = dp[i-1][j];
	}
      }

    }
    /*   
    ascent(i, 0, n+1) {
      ascent(j, 0, w_max+1) {
	printf("%3d ", dp[i][j]);
      }
      puts("");
    }
    */
    cout << "Case " << count << ":" << endl;
    cout << dp[n][w_max] << endl;
    cout << w_sum.second << endl;
    
  }
  return 0;
}

Measured memory_bytes: 40744