akhauriyash/Code-Regression huggingface dataset:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n = int(input())

g = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

lst = [[], [], []]
for i in range(1, n+1):
    lst[i % 3].append(i)

p = [0]*n

depth = [-1]*n
depth[0] = 0

q = [0]

cnt = [1, 0]

while q:
    v = q.pop()
    for w in g[v]:
        if depth[w] != -1:
            continue
        depth[w] = depth[v] + 1
        cnt[depth[w] % 2] += 1
        q.append(w)


ans = [0]*n

if cnt[0] <= n//3:
    ans[0] = lst[0].pop()
    q = [0]
    while q:
        v = q.pop()
        for w in g[v]:
            if ans[w] != 0:
                continue
            if depth[w] % 2 == 0:
                ans[w] = lst[0].pop()
            else:
                if lst[1]:
                    ans[w] = lst[1].pop()
                elif lst[2]:
                    ans[w] = lst[2].pop()
                else:
                    ans[w] = lst[0].pop()
            q.append(w)
elif cnt[1] <= n//3:
    ans[0] = lst[1].pop()
    q = [0]
    while q:
        v = q.pop()
        for w in g[v]:
            if ans[w] != 0:
                continue
            if depth[w] % 2 != 0:
                ans[w] = lst[0].pop()
            else:
                if lst[1]:
                    ans[w] = lst[1].pop()
                elif lst[2]:
                    ans[w] = lst[2].pop()
                else:
                    ans[w] = lst[0].pop()
            q.append(w)
else:
    ans[0] = lst[2].pop()
    q = [0]
    while q:
        v = q.pop()
        for w in g[v]:
            if ans[w] != 0:
                continue
            if depth[w] % 2 != 0:
                if lst[1]:
                    ans[w] = lst[1].pop()
                else:
                    ans[w] = lst[0].pop()
            else:
                if lst[2]:
                    ans[w] = lst[2].pop()
                else:
                    ans[w] = lst[0].pop()
            q.append(w)

print(*ans)


Measured memory_bytes: 101196
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define P pair<ll,ll>
#define lvector vector<ll> 
#define rep(i,n) for(ll (i)=0; i<(n); ++(i))
#define print(a) cout << (a) << endl

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n,a=0,ans=0; cin>>n;
  cin>>ans;
  rep(i,n-1) {cin>>a;ans=__gcd(ans,a);}
  print(ans);
  return 0;
}


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

const int mod = 1e9 + 7;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	
	vector<int> cnt(n);
	for (int i = 0; i < n; i++) {
		int t;
		cin >> t;
		cnt[t]++;
	}
	
	vector<int> foo(n);
	for (int i = 0; i < n; i++) {
		foo[abs(i - (n - 1 - i))]++;
	}

	int ans = 1;
	for (int i = 0; i < n; i++) {
		if (cnt[i] != foo[i]) {
			ans = 0;
		}
		if (cnt[i] == 2) {
			ans *= 2;
			ans %= mod;
		}
	}
	cout << ans << endl;
}


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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2018/03/02  Problem: 001_agc_b / Link: https://agc001.contest.atcoder.jp/tasks/agc001_b?lang=en  ----- */
/* ------問題------

高橋君は 1 辺の長さが N の 3 枚の鏡を正三角形状に組み合わせました。 三角形の頂点をそれぞれ a,b,c とします。
高橋君は、辺 ab 上の頂点 a から X の点から、辺 bc と平行に不思議な光を発射しました。 不思議な光は、普通の光と同じように真っすぐ進み、鏡に当たると反射するのですが、不思議な光がすでに通った点に当たったときにも反射をします。 例えば、N=5,X=2 のとき、不思議な光の軌跡は図の黄色い矢印のようになります。
このように不思議な光を発射した時、不思議な光は必ず発射した点に戻ってくることが証明できます。 このとき、光の軌跡の長さが全体でいくらになるかを求めて下さい。

-----問題ここまで----- */
/* -----解説等-----

あまりに対して愚直にシュミレーションをしていく
GCDっぽい…

解説↓
また，光の軌跡が三角形の集合となり，三角形の辺の長さの和が下図より N −
gcd(N, X) となることに気付くと，答えが 3(N −gcd(N, X)) であることがわかる．(らしい)

----解説ここまで---- */

LL N, X;

LL ans = 0LL;

LL f(LL x, LL n) {
	if (x == 0 || n == 0)return -(x + n);
	if (x > n)return f(n, x);
	LL c = n / x;
	return 2 * c*x + f(x, n - c*x);
}

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

	cin >> N >> X;
	ans = N + f(X, N - X);

	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define deb(x) cout<<#x<<" "<<x<<endl;
#define ll long long int
#define ld long double
#define fo(i, n) for(ll i = 0; i<n; i++)
#define Fo(i, a, n) for(ll i = a; i<n; i++)
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define pi pair<int, int>
#define pl pair<ll, ll>
#define u_m unordered_map
#define u_s unordered_set
#define p_q priority_queue
using namespace std;
const int N = 1e5+2;
ll dp[N][3];
const ll MOD = 1e9+7;
void solve()
{
	int n;
	cin>>n;
	int a[n+1], b[n+1], c[n+1];
	Fo(i, 1, n+1)
		cin>>a[i]>>b[i]>>c[i];
	dp[1][0] = a[1];
	dp[1][1] = b[1];
	dp[1][2] = c[1];
	Fo(i, 2, n+1)
	{
		dp[i][0] = a[i]+max(dp[i-1][1], dp[i-1][2]);
		dp[i][1] = b[i]+max(dp[i-1][0], dp[i-1][2]);
		dp[i][2] = c[i]+max(dp[i-1][0], dp[i-1][1]);
	}
	cout<<max(dp[n][0], max(dp[n][1], dp[n][2]))<<endl;
}
int main()
{
    ios::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);
    int t;
    //cin>>t;
    //while(t--)
		solve();	
    return 0;
}


Measured memory_bytes: 3840
#include<iostream>

using namespace std;

int main(){

	int a, b;

	cin >> a >> b;

	if( a < b ) cout << "a < b" << endl;

	else if( a > b ) cout << "a > b" << endl;

	else if( a == b ) cout << "a == b" << endl;

	return 0;

}

Measured memory_bytes: 1156
#ifdef DBG1
#define _GLIBCXX_DEBUG
#endif

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <functional>

#ifdef DBG1
#define dbg(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define dbg(...)
#endif

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <ll, int> pli;

const int P = 998244353;

int sum(int a, int b) {
  if ((a += b) >= P) {
    a -= P;
  }
  return a;
}

int diff(int a, int b) {
  if ((a -= b) < 0) {
    a += P;
  }
  return a;
}

int prod(int a, int b) {
  return int(ll(a) * b % P);
}

int power(int a, int n) {
  int b = 1;
  while (n) {
    if (n & 1) { b = prod(a, b); }
    a = prod(a, a);
    n /= 2;
  }
  return b;
}

int inv(int a) {
  return power(a, P - 2);
}

int quotient(int a, int b) {
  return prod(a, inv(b));
}

int &add(int &a, int b) {
  return a = sum(a, b);
}

int &subtract(int &a, int b) {
  return a = diff(a, b);
}

int &mult(int &a, int b) {
  return a = prod(a, b);
}

int &div(int &a, int b) {
  return a = quotient(a, b);
}

ll gcd(ll a, ll b) {
  if (b == 0) {
    return a;
  } else {
    return gcd(b, a % b);
  }
}

bool solve() {
  int n;
  if (scanf("%d", &n) != 1) {
    return false;
  }

  const int MAX_POW2 = 30;
  const int MAX_POW5 = 30;

  int a[100][100]{};
  for (int i = 0; i < n; ++i) {
    static char s[100];
    scanf("%s", s);
    ll P = 0;
    ll Q = 1;
    bool has_dot = false;
    for (int j = 0; s[j]; ++j) {
      if (s[j] == '.') {
        has_dot = true;
      } else {
        P = P * 10 + (s[j] - '0');
        if (has_dot) {
          Q *= 10;
        }
      }
    }

    ll X = gcd(P, Q);
    P /= X;
    Q /= X;

    int pow2 = 0;
    int pow5 = 0;
    while (P % 2 == 0) {
      pow2++;
      P /= 2;
    }
    while (P % 5 == 0) {
      pow5++;
      P /= 5;
    }
    while (Q % 2 == 0) {
      pow2--;
      Q /= 2;
    }
    while (Q % 5 == 0) {
      pow5--;
      Q /= 5;
    }

    a[pow2 + MAX_POW2][pow5 + MAX_POW5]++;
  }

  ll res = 0;
  for (int i2 = -MAX_POW2; i2 <= MAX_POW2; ++i2) {
    for (int j2 = -MAX_POW2; j2 <= MAX_POW2; ++j2) {
      if (i2 + j2 < 0) { continue; }
      for (int i5 = -MAX_POW5; i5 <= MAX_POW5; ++i5) {
        for (int j5 = -MAX_POW5; j5 <= MAX_POW5; ++j5) {
          if (i5 + j5 < 0) { continue; }

          ll x = a[i2 + MAX_POW2][i5 + MAX_POW5];
          ll y = a[j2 + MAX_POW2][j5 + MAX_POW5];

          if (i2 == j2 && i5 == j5) {
            res += x * (x - 1);
          } else {
            res += x * y;
          }
        }
      }
    }
  }
  printf("%lld\n", res / 2);
  return true;
}

int main() {

  while (solve()) {
  }
  return 0;
}


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

using namespace std;

#define MAX_V 1000
#define INF 100000000000000

struct edge {
    long long from; //出発点
    long long to;   //到達点
    long long cost; //移動コスト
};

long long V; //頂点の数
long long E; //辺の数
long long d[MAX_V +1]; //始点からそこまで行くのにかかるコスト
vector<edge> edges; //移動の情報を保存する
bool negative_cycle=0;

vector<long long> Grainv[1001];
bool cangoal[1001];

void bellman_ford(long long S){
    fill(d, d+V+1, INF); //すべての頂点をINFにする
    d[S] = 0; //始点を0にする
    long long i;
    for (i = 0; i < V; i++) {
        for (long long j = 0; j < (long long)edges.size(); j++) {

            struct edge e = edges[j];

            if ((d[e.to] > d[e.from] + e.cost)&&(d[e.from]<INF)) {  //移動した後のコストが小さいと、頂点のコストを更新：ただしfromがINFでないとする
                d[e.to] = d[e.from] + e.cost;
                if(cangoal[e.from]==1){
                    if (i == V-1) {         //頂点の数と同じ回数ループすると、負の閉路があるのでループをぬける
                        negative_cycle=1;
                        break;
                    } 
                }
            }
        }
    }
}

void dfs_for_goal(long long v){
    long long i;
    for(i=0; i<Grainv[v].size(); i++){
        if(cangoal[Grainv[v][i]]==0){
            cangoal[Grainv[v][i]]=1;
            dfs_for_goal(Grainv[v][i]);
        }
    }
    
}

int main()
{
    cin >> V;
    cin >> E;

    long long S=1; //始点
    long long G=V; //終点

    long long i;
    for (i = 0; i < E; i++) {
        struct edge add;
        cin >> add.from;
        cin >> add.to;
        cin >> add.cost;
        add.cost=-add.cost;
        edges.push_back(add);

        Grainv[add.to].push_back(add.from);
    }

    fill(cangoal,cangoal+V+1,0);
    cangoal[G]=1;
    dfs_for_goal(G);

    bellman_ford(S);

    if(negative_cycle==0){    
        cout <<  -d[G] << endl;
    }else{
        cout << "inf" << endl;
    }
    system("pause");
    return 0;
}


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

const int MAXN = 100005;

int N, Q;
int T[MAXN], L[MAXN], P[MAXN][20];  // direct parent, depth, ancestor
vector<int> adjList[MAXN];

void dfs(int node = 0, int depth = 0) {
    L[node] = depth;
    for (int i = 0; i < adjList[node].size(); i++) {
        int child = adjList[node][i];
        dfs(child,depth+1);
    }
}

int query(int u, int v) {
    if (L[u] < L[v])
        swap(u,v);

    int LOG2;
    for (LOG2 = 1; 1 << LOG2 <= L[u]; LOG2++); LOG2--;

    for (int i = LOG2; i >= 0; i--)
        if (L[u] - (1 << i) >= L[v])
            u = P[u][i];

    if (u == v)
        return u;

    for (int i = LOG2; i >= 0; i--)
        if (P[u][i] != -1 && P[u][i] != P[v][i])
            u = P[u][i], v = P[v][i];

    return T[u];
}

int main() {

    scanf("%d",&N);
    for (int u = 0, M; u < N; u++) {
        scanf("%d",&M);
        for (int i = 0, v; i < M; i++) {
            scanf("%d",&v);

            T[v] = u;
            adjList[u].push_back(v);
        }
    }

    // rooted at 0
    dfs();

    for (int i = 1; i <= N; i++)
        P[i][0] = T[i];
    for (int j = 1; 1 << j < N; j++)
        for (int i = 1; i <= N; i++)
            P[i][j] = P[P[i][j-1]][j-1];

    scanf("%d",&Q);
    for (int i = 0, u, v; i < Q; i++) {
        scanf("%d%d",&u,&v);
        printf("%d\n", query(u,v));
    }

    return 0;
}

Measured memory_bytes: 18368
#include <bits/stdc++.h>
using namespace std;
#define pi acos(-1)
#define IOS ios_base::sync_with_stdio(0); cin.tie(); cout.tie();
#define ff first
#define ss second
#define pb push_back
#define debug(val) cerr << "The value of " << #val << " is = " << val << '\n';
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1e9 + 7;
const ll inf = 0x3f3f3f3f;
const ll mininf = -922337203685477;
const ll nax = 0;
int n, m, x[55], y[55], a[55], b[55];

int main(){
	IOS
	cin >> n >> m;	
	for(int i=0;i<n;i++){
		cin >> x[i] >> y[i];
	}
	for(int i=0;i<m;i++){
		cin >> a[i] >> b[i];
	}
	for(int i=0;i<n;i++){
		int temp;
		int mins=inf;
		for(int j=0;j<m;j++){
			int manhattan=abs(x[i]-a[j])+abs(y[i]-b[j]);
			if(manhattan<mins) temp=j+1;	
			mins=min(mins, manhattan);
		}
		cout << temp << '\n';
	}
}


Measured memory_bytes: 3588
n = int(input())
f = [list(map(int,input().split())) for i in range(n)]
p = [list(map(int,input().split())) for i in range(n)]
ans = -float("inf")
for i in range(1,2**10):
    now = 0
    for j in range(n):
        cou = 0
        for k in range(10):
            if (i >> k & f[j][k]) == 1:
                cou += 1
        now += p[j][cou]
    ans = max(ans,now)
print(ans)


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

int main(){
   ll n,k;
    ll h[2*100000+1];
    cin>>n>>k;
    k--;
    for(int i=0;i<n;i++){
        cin>>h[i];
    }
    sort(h,h+n);
    ll ans=1000000000;
    for(int i=0;i<n-k;i++){

        ans=min(ans,-h[i]+h[i+k]);

    }
    cout<<ans<<endl;
    return 0;
}

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

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector <int> h(n), dp(n+1, 1e9+7);
    for (int i = 0; i < n; ++i) cin >> h[i];
    dp[0] = 0;
    for (int i = 0; i < n; ++i)
    {
        for (int j : {i+1, i+2})
        {
            dp[j] = min(dp[j], dp[i]+abs(h[i]-h[j]));
        }
    }
    cout << dp[n-1] << '\n';
}

Measured memory_bytes: 3980
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,k;
    scanf("%d %d",&k,&n);
    int a[n];
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    int max=a[0]+k-a[n-1];
    for(int i=1;i<n;i++)
    {
        if(a[i]-a[i-1]>max)
            max=a[i]-a[i-1];
    }
    printf("%d\n",k-max);
    return 0;
}


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

int main(){
  int a, b, c, x, y;
  cin >> a >> b >> c >> x >> y;
  int tmp, ans = 1000000000;
  for(int i = 0; i <= 200000; i++){
    tmp = c*2*i + a*max(0, x-i) + b*max(0, y-i);
    ans = min(ans, tmp);
  }
  cout << ans << endl;

}


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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int a, b;
  cin >> a >> b;
  for (int i = 1; i < 1005; i++) {
    int foo = (int)floor(i * 0.08);
    int bar = (int)floor(i * 0.1);
    if (foo == a && bar == b) {
      cout << i << '\n';
      return 0;
    }
  }
  cout << "-1\n";
  return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
	public static ArrayList<String> s = new ArrayList<String>();
	public static void main(String[] args) throws IOException {
		FastScanner in = new FastScanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int n= in.nextInt();
		int [] a= new int[n];
		HashMap<Integer, Integer> c= new HashMap<>();
		for (int i = 0; i < a.length; i++) {
			a[i]= in.nextInt();
			if(c.containsKey(a[i])){
				c.put(a[i], c.get(a[i])+1);
			}
			else{
				c.put(a[i], 1);
			}
		}
		Arrays.sort(a);
		TreeSet<Integer> r= new TreeSet<>();
		int have= 0;
		int i= a.length-1;
		for (i = a.length-1; i >=0;) {
			int numof= c.get(a[i]);
			if(numof>=4&&have==0){
				System.out.println((long) a[i]*a[i]);
				return;
			}
			else if(numof>=2){
				r.add(a[i]);
				have+= Math.min(numof, 2);
			}
			i-=numof;
			//System.out.println(i);
		}
		long res=0;
		if(r.size()>=2) res= (long) r.pollLast()*r.pollLast();
		System.out.println(res);

	}
	static class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		public FastScanner(InputStream in) {
			br = new BufferedReader(new InputStreamReader(in));
			st = new StringTokenizer("");
		}

		public double nextDouble() throws NumberFormatException, IOException {
			return Double.parseDouble(next());
		}

		public String next() throws IOException {
			if (!st.hasMoreTokens()) {
				st = new StringTokenizer(br.readLine());
				return next();
			}
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
	}
}



Measured memory_bytes: 45852
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i,n) for(int i=0, i##_len=(int)(n); i<i##_len; i++)
#define reps(i,n) for(int i=1 , i##_len=(int)(n);i<=i##_len;i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--)
#define rreps(i,n) for(int i=((int)(n));i>0;i--)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define solve(a) ((a)?"Yes":"No")
typedef vector<long long> V;
typedef vector<V> VV;
typedef pair<long long , long long> P;
typedef vector<P> VP;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1;} return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1;} return 0;}
const long long INFLL = 1LL<<55;
const int INF = 1<<30;
const double PI=acos(-1);
//ワーシャルフロイゼ法(隣接行列を受け取り、それぞれの最短を受け取る、size:10^2-)
vector<vector<long long>> WarshallFloyd(vector<vector<long long>> pathmatrix){
	int index=pathmatrix.size();
	vector<vector<long long >>res=pathmatrix;
	for (int a = 0; a < index; a++){
		for (int b = 0; b < index; b++){
			for (int c = 0; c < index; c++){ 
				chmin(res[b][c], res[b][a] + res[a][c]);
			}
		}
	}
	return (res);
}
int main(){
	int v,e;
	cin >>v>>e;
	VV path(v,V(v,INFLL));
	rep(i,v){
		path[i][i]=0LL;
	}
	int s,t;
	ll d;
	rep(i,e){
		cin>>s>>t>>d;
		path[s][t]=d;
	}
	path=WarshallFloyd(path);
	VV res=WarshallFloyd(path);
	bool con=true;
	rep(i,v){
		rep(j,v){
			con=(con&(res[i][j]==path[i][j]));
		}
	}
	if(!con){cout<<"NEGATIVE CYCLE"<<endl; return 0;}
	rep(i, v)
	{
		rep(j, v)
		{
			if(path[i][j]>(ll)1e10){
				cout<<"INF";
			}else{
				cout<<path[i][j];
			}
			if(j!=v-1){
				cout<<" ";
			}else{
				cout<<endl;
			}
		}
	}
}


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

int main() {
    int n, ac, wa, tle, re;
    ac = wa = tle = re = 0;
    char c[5];
    scanf("%d", &n);
    rep(step, n) {
        scanf("%s", c);
        switch (c[0]) {
        case 'A':
            ac++;
            break;
        case 'W':
            wa++;
            break;
        case 'T':
            tle++;
            break;
        case 'R':
            re++;
            break;
        default:
            break;
        }
    }
    printf("AC x %d\n", ac);
    printf("WA x %d\n", wa);
    printf("TLE x %d\n", tle);
    printf("RE x %d\n", re);
    return 0;
}


Measured memory_bytes: 3788
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int main(int argc, char *argv[])
{
	int N, M;

	scanf("%d %d", &N, &M);
	vector<int> v(0);

	for (int i=0; i<M; i++)
	{
		int t;
		scanf("%d", &t);
		v.push_back(t);
	}
	sort(v.begin(),v.end());
	
	vector<int> d(0);
	for (int i=0; i<M-1;i++)
	{
		d.push_back(v[i+1]-v[i]);
	}
	sort(d.begin(),d.end());

	int ret=0;
	for (int i=0; i<M-N;i++)
	{
		ret+=d[i];
	}

		
	printf("%d", ret);
	return 0;
}

Measured memory_bytes: 1400
#include <iostream>
#include <vector>
#include <cstdlib>
#include <iomanip>

using namespace std;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

const long long INF = 1LL << 60;

// 入力
int N;
long long h[110000][3];

// DP テーブル
long long dp[110000][3];

int main() 
{
	cin >> N;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < 3; ++j) {
			cin >> h[i][j];
		}
	}
  // 幸福度の各区分の合計値を注目する。
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < 3; ++j) {
			for (int k = 0; k < 3; ++k) {
				if (j == k) {
					continue;
				}
				chmax(dp[i + 1][k], dp[i][j] + h[i][k]);
			}
		}
	}
	long long res = 0;
	for (int j = 0; j < 3; ++j) {
		chmax(res, dp[N][j]);
	}
	cout << res << endl;
}


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

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) for(i64 i = 1; i <= n; ++i)
#define RREP(i, n) for(i64 i = n - 1; i >= 0 ; --i)
#define RREPS(i, n) for(i64 i = n; i >= 1; --i)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define pb push_back
#define mp make_pair
#define F first
#define S second

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }


struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;


#define MAX_N 2999
i64 N;
f64 dp[2 * MAX_N][2 * MAX_N];
f64 P[MAX_N];

int main() {
    cin >> N;
    REP(i, N) cin >> P[i];

    REP(i, 2 * N) REP(j, 2 * N) dp[i][j] = 0;
    dp[0][0] = 1.0;

    REP(i, N) {
        for (i64 j = 0; j <= i; j++) {
            dp[i + 1][j + 1] += dp[i][j] * P[i];
            dp[i + 1][j] += dp[i][j] * (1 - P[i]);
        }
    }

    double ans = 0;
    for (i64 j = (N + 1) / 2; j <= N; j++) {
        ans += dp[N][j];
    }
    cout << fixed << setprecision(10) << ans << endl;

    return 0;
}

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

using namespace std;

int main(){
    int x, y, a, b, c;
    cin >> x >> y >> a >> b >> c;
    vector<int64_t> P(a), Q(b), R(c);
    for (int i = 0; i < a; i++)
        scanf("%d", &P[i]);
    for (int i = 0; i < b; i++)
        scanf("%d", &Q[i]);
    for (int i = 0; i < c; i++)
        scanf("%d", &R[i]);
        
    nth_element(P.begin(), P.begin() + x, P.end(), greater<int64_t>());
    nth_element(Q.begin(), Q.begin() + y, Q.end(), greater<int64_t>());

    for (int i = 0; i < x; i++)
        R.push_back(P[i]);

    for (int i = 0; i < y; i++)
        R.push_back(Q[i]);

    nth_element(R.begin(), R.begin() + x + y, R.end(), greater<int64_t>());
    cout << accumulate(R.begin(), R.begin() + x + y, 0L) << endl;
}

Measured memory_bytes: 6384
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<math.h>
#include<set>
#include<map>
#include<time.h>
#include<stack>
#include<queue>
#include<stdlib.h>
#include<string.h>
#include<vector>
#define LL long long
#define  long long
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const double INF=1e9+7;
int Find[10000];
int find(int x) {return Find[x]==x?x:Find[x]=find(Find[x]);}
char a[100005];
int main()
{
    scanf("%s",a);
    int n=strlen(a);
    stack<char>S;
    int ans=0;
    for(int i=0;i<n;i++)
    {
        if(S.empty())
        {
            S.push(a[i]);
        }
        else{
            char temp=S.top();
            if(a[i]!=temp)
            {
                ans+=2;
                S.pop();
            }
            else S.push(a[i]);
        }
    }
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<utility>
#include<set>
#include<stack>
#include<queue>
#include<deque>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<bitset>
#include<sstream>
#include<list>
#include<climits>

using namespace std;
#define rep(i,i0,n) for(int i=(i0);i<(int)(n);++i)
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vii;
typedef long long ll;

ll a[100010],b[100010],d[100010];
int n;
ll c;
ll x[100010];
int v[100010];

ll solve(){
    rep(i,0,n)a[i]= i>0? v[i]+a[i-1]:v[i];
    for(int i=n-1;i>=0;i--)b[i] = i<n-1 ? v[i]+b[i+1]: v[i];
    d[n-1] = b[n-1] - (c-x[n-1]);
    for(int i=n-2;i>=0;i--){
        d[i] = b[i] - (c-x[i]);
        d[i] = max(d[i],d[i+1]);
    }
    ll ans = 0;
    rep(l,0,n){
        ll sum = a[l] -  x[l];
        ans = max(ans, sum);
        sum -= x[l];
        if(l < n-1){
            sum += d[l+1];
            ans = max(ans, sum);
        }
    }
    return ans;
}


int main(){
    cin>>n>>c;
    rep(i,0,n)cin>>x[i]>>v[i];
    ll ans=solve();
    reverse(v,v+n);
    rep(i,0,n)x[i]=c-x[i];
    reverse(x,x+n);
    ans = max(ans, solve());
    cout<<ans<<endl;
	return 0;
}



Measured memory_bytes: 3712
/*
 * You have N kinds of items that you want to put them into a knapsack. Item i
 * has value vi and weight wi.
 *
 * You want to find a subset of items to put such that:
 *
 * The total value of the items is as large as possible.
 * The items have combined weight at most w, that is capacity of the knapsack.
 * You can select as many items as possible into a knapsack for each kind.
 * Find the maximum total value of items in the knapsack.
 *
 * Input
 * N w
 * v1 w1
 * v2 w2
 * :
 * vN wN
 * The first line consists of the integers N and w. In the following lines, the
 * value and weight of the i-th item are given.
 *
 * Output
 * Print the maximum total values of the items in a line.
 *
 * Constraints
 * 1 ≤ N ≤ 100
 * 1 ≤ vi ≤ 1000
 * 1 ≤ wi ≤ 1000
 * 1 ≤ w ≤ 10000
 */

#include <algorithm>
#include <iostream>
#include <vector>
#define MAXN 110
#define MAXW 10010

using namespace std;

int dp[MAXN][MAXW];

int main() {
  for (int i = 0; i < MAXN; ++i)
    fill(dp[i], dp[i] + MAXW, 0);
  int n, w;
  cin >> n >> w;
  struct item {
    int v, w;
  };
  vector<item> knap;
  for (int i = 0, nextv, nextw; i < n; ++i) {
    cin >> nextv >> nextw;
    knap.push_back({nextv, nextw});
  }
  for (int k = 1; k <= w; ++k)
    dp[0][k] = k >= knap[0].w ? knap[0].v + dp[0][k - knap[0].w] : 0;
  for (int i = 1; i < n; ++i)
    for (int k = 1; k <= w; ++k)
      dp[i][k] = max(k >= knap[i].w ? knap[i].v + dp[i][k - knap[i].w] : -1,
                     dp[i - 1][k]);
  cout << dp[n - 1][w] << endl;
}


Measured memory_bytes: 7460
#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 INF 1e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
#define downque(que)  priority_queue<ll> que;
#define upque(que) priority_queue<ll, vector<int>, greater<int>> que;


int main(){
   ll n,x; cin>>n>>x;
   ll a[n];
   ll sum=0;

   REP(i,n)cin>>a[i];
   REP(i,n-1){
      
      if(a[i]+a[i+1]>x){
         sum+=a[i]+a[i+1]-x;
         
         if(x>=a[i])a[i+1]=x-a[i];
         else{
          a[i+1]=0;    
          a[i]=x;
         }
      }
   }
  cout<<sum<<endl;
} 

 

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

typedef long long ll;

#define SIZE_OF_ARRAY(array) (sizeof(array) / sizeof(array[0]))
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define AA(i) cout << i << endl;
#define AS(i) cout << i << " ";

const int INF = 1001001001;
const double PI = 3.14159;

using namespace std;

int main() {

    int n;
    cin >> n;

    int ac = 0;
    int wa = 0;
    int tle = 0;
    int re = 0;

    string a;

    rep(i, n) {
        cin >> a;

        if (a == "AC")
            ac++;
        else if (a == "WA")
            wa++;
        else if (a == "TLE")
            tle++;
        else if (a == "RE")
            re++;
    }

    cout << "AC x " << ac << endl << "WA x " << wa << endl << "TLE x " << tle << endl << "RE x " << re << endl;
}

Measured memory_bytes: 3620
#include<iostream>
using namespace std;
typedef long long ll;

int main(){
    int N;
    cin >> N;
    ll a[N];
    for(int i=0;i<N;i++){
        cin >> a[i];
    }
    int cnt=0;
    int cnt_e=0;
    for(int i=0;i<N;i++){
        int x=a[i];
        if(x%2==0){
            while(true){
                x/=2;
                if(x%2!=0) break;
                cnt++;
            }
            cnt_e++;
        }
    }
    cout << cnt+cnt_e << endl;
}

Measured memory_bytes: 384
n = int(input())
lix = []
liv = []
for i in range(n):
    x,v = input().split()
    lix.append(float(x))
    liv.append(v)

ans = 0

for i in range(n):
    if liv[i] == "JPY":
        ans += lix[i]
    else:
        ans += lix[i]*380000

print(ans)

Measured memory_bytes: 3064
#include <stdio.h>
int main(void)
{
  int A, B, K, a, ans, i=0;
  scanf("%d %d %d", &A, &B, &K);
  for(a=A; a>0; a--){
    if(A%a==0){
      if(B%a==0){
        ans = a;
        i++;
      }
    }
    if(i==K){
    break;
    }
  }
  printf("%d", ans);
  return 0;
}

Measured memory_bytes: 128
(function main(){
  const lines = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split('\n');
  const n = Number(lines.shift());
  const arr = lines.shift().split(' ');
  buildMaxHeap(arr);
  console.log(' ' + arr.join(' '));
})();

function buildMaxHeap(arr) {
  const n = arr.length;
  const maxHeapify = (i) => {
    let left, right, largest = i;
    left = 2 * i + 1;
    right = 2 * i + 2;
    if (left < n && Number(arr[left]) > Number(arr[largest])) largest = left;
    if (right < n && Number(arr[right]) > Number(arr[largest])) largest = right;
    if (largest != i) {
      arr[largest] = [arr[i], arr[i] = arr[largest]][0];
      maxHeapify(largest);
    }
  };
  for (let i = Math.floor(n / 2 - 1); i >= 0; i--) maxHeapify(i);
}



Measured memory_bytes: 88300
#include <stdio.h>
#include <string.h>

int Check(char *S, int s, int e);

int main(void) {
   
   char S[200];
   
   scanf("%s", S);
   
   int N = strlen(S);
   int ans = Check(S, 0, N - 1);
   
   ans = ans + Check(S, 0, (N - 1)/2 - 1);
   ans = ans + Check(S, (N + 3)/2 - 1, N - 1);
   /*
   printf("%d\n",Check(S, 0, N - 1));
   printf("%d\n",Check(S, 0, (N - 1)/2 - 1));
   printf("%d\n",Check(S, (N + 3)/2 - 1, N - 1));
   */
   if (ans == 0) {
      printf("Yes\n");
   }
   else {
      printf("No\n");
   }
   
   
   return 0;
}

int Check(char *S, int s, int e) {
   
   int i;
   int flag = 0;
   
   for (i = s; i <= e; i++) {
      if (S[i] == S[e - i + s]) {
         flag = 0;
      }
      else {
         flag = 1;
         break;
      }
   }
   
   return flag;
   
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef   long long ll;
typedef   unsigned long long ull ;
typedef   double dll ;
#define   mp make_pair
#define   pb push_back
#define   ff first 
#define   ss second
#define   IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define   endl "\n" 
#define   pll pair<ll, ll>
#define   all(x) x.begin(), x.end()
#define   vll vector<ll> 


int main() 
{ 
    IOS
    ll n,m,k;
    cin>>n>>m>>k;
    vll a(n+1);
    a[0]=0;
    ll idx=0,now=0;
    bool flag=false;
    for(ll i=1;i<n+1;i++)
    {
        cin>>a[i];
        if(a[i]+now<=k and !flag)
        {
            now+=a[i];
            idx++;
        }
        else
        {
            flag=true;
        }
    }
    ll ans=idx;
    ll ct=idx;

    for(ll i=0;i<m;i++)
    {
        ll x;
        cin>>x;
        now+=x;
        if(now<=k) ct++;

        if(now>k)
        {
            while(now>k and idx>0)
            {
                now-=a[idx];
                idx--;
                ct--;
            }
            if(now<=k) ct++;
        }
        ans=max(ans,ct);

    }
    cout<<ans<<endl;


    return 0; 
} 
/*
3 4 730
60 90 120
80 150 80 150
*/

Measured memory_bytes: 4780
#include <bits/stdc++.h>
using namespace std;
char s[100005];
int f[27];
int main () {
	scanf("%s", s);
	int n=strlen(s);
	for (int i=0; i<n-1; i++) {
		if (s[i]==s[i+1]) {
			printf("%d %d\n", i+1, i+2);
			return 0;
		}
		if (s[i]==s[i+2]) {
			printf("%d %d\n", i+1, i+3);
			return 0;
		}
	}
	printf("-1 -1\n");
	return 0;
}

Measured memory_bytes: 384
using System;

namespace atcoder
{
    public class atcoder
    {
        public static void Main()
        {
            int n = int.Parse(Console.ReadLine());
            if (n < 1200) Console.WriteLine("ABC");
            else if (n < 2800) Console.WriteLine("ARC");
            else Console.WriteLine("AGC");
        }
    }
}

Measured memory_bytes: 13140
// abc062-b
object Main extends App {
  val Array(h,w) = io.StdIn.readLine.split(" ").map(_.toInt)
  val as = for (_ <- 1 to h) yield io.StdIn.readLine

  println("#" * (w+2))
  for (a <- as) println(("#"+:a:+"#").mkString)
  println("#" * (w+2))
}

Measured memory_bytes: 54792
#include <iostream>
#include <bitset>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <regex>
#include <iomanip>
#include <climits>
#include <utility>
#include <queue>
using namespace std;
using ll = long long int;
using dd = long double;
const ll MOD = 1e9 + 7;
const dd PI = 3.1415926435;

ll gcd(ll a, ll b)
{
    if (a % b == 0)
    {
        return b;
    }
    return gcd(b, a % b);
}

ll fact(ll n)
{
    if (n == 0)
    {
        return 1;
    }
    if (n == 1)
    {
        return 1;
    }
    return n * fact(n - 1) % MOD;
}

ll pow_fast(ll n, ll k)
{
    if (k == 0)
    {
        return 1;
    }
    if (k == 1)
    {
        return n;
    }

    if (k % 2 == 0)
    {
        ll tmp = pow_fast(n, k / 2LL);
        return tmp * tmp % MOD;
    }
    else
    {
        ll tmp = pow_fast(n, k / 2LL);
        tmp *= tmp;
        tmp %= MOD;
        return tmp * n % MOD;
    }
}

map<ll, ll> sosuu(ll n)
{
    map<ll, ll> res;
    for (ll i = 2; i * i <= n; i++)
    {
        while (n % i == 0)
        {
            res[i] += 1;
            n /= i;
        }
    }
    if (n != 1)
    {
        res[n] += 1;
    }
    return res;
}

int main()
{
    ll A, V;
    ll B, W;
    cin >> A >> V >> B >> W;
    ll T;
    cin >> T;

    bool ok = false;

    if (A > B && (A - T * V) <= (B - T * W))
    {
        ok = true;
    }
    if (A < B && (A + T * V) >= (B + T * W))
    {
        ok = true;
    }

    if (ok)
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef pair<int, int> Pint;
typedef pair<int64_t, int64_t> Pll;

int main() {
    int64_t N, A, B, C, D, E, a = 0;
    cin  >> N >> A >> B >> C >> D >> E;
    if (N % min({A, B, C, D, E}) != 0) {
        a++;
    }
    cout << N / min({A, B, C, D, E}) + 4 + a << endl;
}


Measured memory_bytes: 256
#include <functional>
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
#include <string>
#include <cstring>
#include <math.h>
using namespace std;


int main() {
   int a;
   int b;
   int c;
 
   cin >> a >> b >> c;
  
   int a1 = a+b;
   int a2 = a-b;
   int a3 = a*b;
  
   int bb[3];
  
   bb[0]=a1;
   bb[1]=a2;
   bb[2]=a3;
     
   sort(bb, bb + 3, greater<int>());
  
  cout << bb[0]<<endl;
   
  return 0;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

var sc = bufio.NewScanner(os.Stdin)

func Scanner() string {
	sc.Scan()
	return sc.Text()
}

func intScanner() int {
	n, _ := strconv.Atoi(Scanner())
	return n
}

func floatScanner() float64 {
	n, _ := strconv.ParseFloat(Scanner(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func stringSliceScanner(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scanner()
	}
	return a
}
func intSliceScanner(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = intScanner()
	}
	return a
}
func larger(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}
func smaller(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
func max(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x < a[i] {
			x = a[i]
		}
	}
	return x
}
func min(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x > a[i] {
			x = a[i]
		}
	}
	return x
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}

var mod int

func main() {
	mod = 1000000007
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	n, k := intScanner(), intScanner()
	a := intSliceScanner(n)
	x := k
	for j := 0; j < k; j++ {
		b := make([]int, n)
		for i := 0; i < n; i++ {
			b[larger(i-a[i], 0)]++
			if i+a[i] < n-1 {
				b[i+a[i]+1]--
			}
		}
		copy(a, b)
		for i := 1; i < n; i++ {
			a[i] = a[i] + a[i-1]
		}
		f := true
		for i := 0; i < n; i++ {
			if !(i-a[i] < 0 && i+a[i] >= n) {
				f = false
			}
		}
		x--
		if f {
			break
		}
	}
	if x > 0 {
		for i := 0; i < n; i++ {
			a[i] = n
		}
	}
	fmt.Println(strings.Trim(fmt.Sprint(a), "[]"))
}


Measured memory_bytes: 13264
x = int(input())
price = [100, 101, 102, 103, 104, 105]
 
dp = [False for _ in range(x + 1)]
 
dp[0] = True

for i in range(1, x + 1):
    for j in range(6):
        if i - price[j] >= 0:
            if dp[i - price[j]]:
                dp[i] = True
                break
    else:
        dp[i] = False
 
if dp[x]:
    print(1)
else:
    print(0)

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

#define REP(i, x, n) for (int i = x; i < (int)(n); i++)
#define rep(i, n) REP (i, 0, n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x.size())
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define uniq(x) x.erase(unique(x.begin(), x.end()), x.end())
#define F first
#define S second
#define mp make_pair
#define eb emplace_back

using namespace std;

typedef long long ll;

// const int INF = 1 << 30;
// const ll INF = 1LL << 60;
// const int MOD = 1000000007;

int main() {
  int N, M;
  cin >> N >> M;
  vector<pair<int, int>> vp;
  rep (i, N) {
    int a, b;
    cin >> a >> b;
    vp.eb(mp(a, b));
  }
  sort(all(vp));

  ll ans = 0;
  int sum = 0;

  rep (i, N) {
    int m = min(M - sum, vp[i].S);
    ans += 1LL * vp[i].F * m;
    sum += m;
    if (sum == M) break;
  }

  cout << ans << endl;
}


Measured memory_bytes: 1400
N, P = gets.split.map(&:to_i)
S = gets.chomp

(puts (0 ... N).inject(0){|r, i| r + (S[i].to_i % P == 0 ? i + 1 : 0)}; exit) if 10 % P == 0

v, f, a = 0, 1, Array.new(P, 0)
a[v] = 1
S.reverse.chars.map(&:to_i).each do |d|
  v = (v + (d * f)) % P
  a[v] += 1
  f = f * 10 % P
end
puts a.inject(0){|s, x| s + x*(x - 1)/2}

Measured memory_bytes: 14612
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int main()
{
   char arr[10000];
   scanf("%s",arr);
   int n = strlen(arr
    );
   if(arr[2]==arr[3] && arr[4]==arr[5])
       printf("Yes");
   else printf("No");


   return 0;
}

Measured memory_bytes: 128
import java.security.KeyStore.TrustedCertificateEntry
import java.util
import java.util.regex.Pattern
import java.util.{ArrayList, Collections, Comparator, List => JList}

import scala.collection.immutable.TreeMap
import scala.math._
import scala.collection.mutable
import scala.collection.mutable.{ArrayBuffer, ListBuffer}
import scala.util.{Failure, Success, Try}

object Main{
  val LINE_SEPARATOR = "\n"
  def main(args: Array[String]): Unit = {
    if (sys.env.getOrElse("TEST", "")=="1"){
      println(test());
    }else{
      val input=io.Source.stdin.getLines().mkString(LINE_SEPARATOR);
      println(solve(input).trim());
    }
  }

  def init (nRows: Int, nCols: Int, default: Int) = Array.tabulate(nRows,nCols)( (x,y) =>  default)

  def sortIgnoreCase1(list: JList[String]): JList[String] = {
    val r = new ArrayList[String](list)
    Collections.sort(r, new Comparator[String] {
      override def compare(o1: String, o2: String): Int = o1.compareToIgnoreCase(o2)
    })
    r
  }

  def solve(input: String): String = {
    val Array(s, w) = input.split(" ").map(_.toInt)
    if (w >= s) "unsafe" else "safe"
  }

  def medianCalculator(seq: Seq[Int]): Int = {
    //In order if you are not sure that 'seq' is sorted
    val sortedSeq = seq.sortWith(_ < _)

    if (seq.size % 2 == 1) sortedSeq(sortedSeq.size / 2)
    else {
      val (up, down) = sortedSeq.splitAt(seq.size / 2)
      (up.last + down.head) / 2
    }
  }

  def factorize(x: Long): List[Long] = {
    def foo(x: Long, a: Long = 2, list: List[Long] = Nil): List[Long] = a*a > x match {
      case false if x % a == 0 => foo(x / a, a    , a :: list)
      case false               => foo(x    , a + 1, list)
      case true                => x :: list
    }
    foo(x)
  }

  def divisors(n: Long): Vector[Long] = {
    val halfList = (1 to sqrt(n).toInt).toVector.filter(_ % n == 0).map(_.toLong)
    val reversedList = if (sqrt(n).floor == sqrt(n)) halfList.reverse.tail.map(n/_) else halfList.reverse.map(n/_)
    halfList ++ reversedList
  }

  def gcd(m: Long, n: Long): Long = n match {
    case 0 => m
    case _ => gcd(n, m % n)
  }
  def lcm(a: Long, b: Long): Long = a * b / gcd(a, b)

  val tests=List(
    """1 2
      |3 1
      |3""".stripMargin -> """YES
                                   |""".stripMargin,
    """1 2
      |3 2
      |3""".stripMargin -> """NO""".stripMargin,
    """1 2
      |3 3
      |3""".stripMargin -> """NO"""
  )

  def test():String= {
    return tests.map{case (i,o)=>(i.trim(),o.trim())}
      .zipWithIndex.map{
      case ((input,outputExpect),i)=>{
        val output=solve(input).trim();
        s"test${i+1}:"+(if(output==outputExpect){
          "Passed"
        }else{
          s"Failed\nexpect:\n${outputExpect}\noutput:\n${output}"
        })
      }}
      .mkString("\n");
  }
}

Measured memory_bytes: 55236
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef vector<int> VI;
const ll MOD = 1000000007;
#define REP(i, n) for(int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()
int main() {
	string s;
	cin >> s;
	int ans = 0, flag = 0;
	for (int i = 0; i < s.length() - 1; i++) {
		if (flag != 2) {
			ans++;
			if (flag == 0 && s[i] == s[i + 1])
				flag = 2;
			if (flag == 1)
				flag = 0;
		}
		else
			flag = 1;
	}
	if (flag != 2)
		ans++;
	cout << ans;
}

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

using namespace std;
#define ll long long
#define ld long double

#define endl '\n'
#define FAST                      \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
const ll mod = 1000000007;
const double PI = 3.141592653589793238463;
const int MAXN = 1e5 + 5;
ll fastPow(ll x, ll b)
{
    if (b == 0)
        return 1;
    else if (!(b & 1))
    {
        return fastPow(x * x, b / 2);
    }
    else
        return x * fastPow(x * x, (b - 1) / 2);
}
//__builtin_popcount ();
struct def
{
    string h = ">";
};
int main()
{
    FAST
        ll x;
        cin>>x;
        ll ans = 2 * (x / 11);
        if(x%11==0)
            return cout << ans, 0;
        if (x % 11 <= 6)
            cout << ans + 1 << endl;
            else 
            {
                cout << ans + 2 << endl;
            }

            return 0;
}

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

typedef long long lint;

#define MAXN 2005

using namespace std;

int n, k;
lint f[MAXN][MAXN], fac[MAXN * MAXN], inf[MAXN * MAXN];
const int mod = 1e9 + 7, N = 4000000;

lint power(lint a, int b) {
    lint res = 1;
    while (b) {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

void init() {
    inf[0] = fac[0] = 1;
    for (int i = 1; i <= N; ++i)
        fac[i] = fac[i - 1] * i % mod;
    inf[N] = power(fac[N], mod - 2);
    for (int i = N - 1; i >= 1; --i)
        inf[i] = inf[i + 1] * (i + 1) % mod;
}

lint C(int n, int m) {
    return fac[n] * inf[n - m] % mod * inf[m] % mod;
}

int main() {
    init();
    scanf("%d%d", &n, &k);
    if (k == 1) {
        puts("1");
        return 0;
    }
    f[0][0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= i; ++j)
            if (!j)
                f[i][j] = f[i - 1][j];
            else
                f[i][j] = (f[i - 1][j] + f[i][j - 1] * C(n * k - (j - 1) * (k - 1) - i - 1, k - 2) % mod * (n - j + 1) % mod) % mod;
    printf("%lld\n", f[n][n]);
}


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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// グラフの辺表現
using Edge = map<pair<int,int>,int>;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

// 最大公約数
ll gcd(ll a,ll b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

// 最小公倍数
ll lcm(ll a, ll b){
    return a*b/gcd(a, b);
}

int main()
{
    cout << fixed << setprecision(15);
    ll N, C;
    cin >> N >> C;

    vector<ll> x(N);
    vector<ll> v(N);

    REP(i, N){
        cin >> x[i] >> v[i];
    }

    vector<P> left(N+1);
    vector<P> right(N+1);

    REP(i, N){
        P p;
        if(i==0){
            p.first = x[0];
            p.second = v[0];
        }
        else{
            p.first = x[i];
            p.second = left[i].second + v[i];
        }
        left[i+1] = p;
    }

    for(ll i=N-1; i>=0; i--){
        P p;
        if(i==N-1){
            p.first = C - x[N-1];
            p.second = v[N-1];
        }
        else{
            p.first = (C - x[i]);
            p.second = right[N-1-i].second + v[i];
        }
        right[N-i] = p;
    }

    P p;
    p.first = 0;
    p.second = 0;
    left[0] = p;
    right[0] = p;

    // cout << "left" << endl;
    // REP(i, N+1){
    //     cout << left[i].first << " " << left[i].second << endl;
    // }

    // cout << "right" << endl;
    // REP(i, N+1){
    //     cout << right[i].first << " " << right[i].second << endl;
    // }


    vector<ll> left1(N+1, 0);
    vector<ll> left2(N+1, 0);
    vector<ll> right1(N+1, 0);  
    vector<ll> right2(N+1, 0);

    ll maxleft = 0;
    ll maxleft2 = 0;
    REP(i, N+1){
        maxleft = max(maxleft, left[i].second -left[i].first);
        left1[i] = maxleft;
    }
    REP(i, N+1){
        maxleft2 = max(maxleft2, left[i].second -left[i].first * 2);
        left2[i] = maxleft2;
    }

    ll maxright = 0;
    ll maxright2 = 0;
    REP(i, N+1){
        maxright = max(maxright, right[i].second -right[i].first);
        right1[i] = maxright;
    }
    REP(i, N+1){
        maxright2 = max(maxright2, right[i].second -right[i].first * 2);
        right2[i] = maxright2;
    }

    ll ans = 0;

    for(ll i=0; i<=N; i++){
        ans = max(ans, left1[i] + right2[N-i]);
        ans = max(ans, right1[i] + left2[N-i]);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 8064