akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>
#include <vector>
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pb push_back
#define in insert
#define er erase
#define fi first
#define se second
#define mp make_pair
#define all(x) x.begin(),x.end()
#define sz(x) (int) x.size()
using namespace std;
typedef vector <int> vi;
typedef vector <vector<int>> vii;
typedef pair<int,int> pii;
typedef double db;
typedef long long ll;
typedef long double ld;

const long double PI=3.141592653589793238462643383279502884;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
int main(){
    fast;
    string s0;
    cin>>s0;
    ll i=s0.length()/2*2-1;
    if (i==s0.length()-1){
        i-=2;
    }
    while (i>0){
        int f=1;
        ll j;
        for (j=0;j<i/2&&f;j++){
            f=s0[j]==s0[j+i/2+1];
        }
        if (f){
            break;
        }
        i-=2;
    }
    cout<<i+1;
    return 0;
}





Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>

#define _GLIBCXX_DEBUG
#define rep(i, n) for (int64_t i = 0; i < (int64_t)(n); i++)
using namespace std;
using vi = vector<int64_t>;
using vvi = vector<vi>;

int main(int argc, const char * argv[]) {
    // fasten cin
    cin.tie(0);
    ios::sync_with_stdio(false);
    // implement
    int64_t a,b;
    cin >> a >> b;
    if(a>8||b>8){
        cout << ":(" << endl;
    }else{
        cout << "Yay!" << endl;
    }
}


Measured memory_bytes: 256
//#include "pch.h"
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <math.h>
#define OO INT_MAX
#define mp(x,y) make_pair(x,y)
#define x first
#define y second
#define ll unsigned long long int
#define pp pair<int,int>
#define heap priority_queue<pp, vector<pp>, greater<pp>>
using namespace std;

int main()
{
	//freopen("test.txt", "r", stdin);
	
	int n;
	vector<int> numbers;
	int in;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> in;
		if (in % 2 == 0)
			numbers.push_back(in);
	}
	for (int element : numbers) {
		if (element % 3 != 0 && element % 5 != 0) {
			cout << "DENIED";
			return 0;
		}
	}
	cout << "APPROVED";
	return 0;
}



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

#define for_(i,a,b) for(int i=(a);i<(b);++i)
#define for_rev(i,a,b) for(int i=(a);i>=(b);--i)

void convert(int x) {
	if (x == 0) {
		cout << 0 << endl;
		return;
	}
	
	int mul = 16777216;
	bool flag = false;
	
	for_rev(i,12,0) {
		if (flag || x / mul > 0) {
			cout << x / mul;
			x -= (x / mul) * mul;
			flag = true;
		}
				
		mul /= 4;
	}
	
	cout << endl;
}

int main() {
	int n;
	while (cin >> n, n != -1) convert(n);
}

Measured memory_bytes: 1160
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        String result = (a == b) ? "a == b" : (a > b) ? "a > b" : "a < b";
        System.out.println(result);
    }
}

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

int N;
vector<int>G[1<<17];
bool vis[1<<17];
void dfs(int u,int p)
{
    for(int v:G[u])
    {
        if(!vis[v])
        {
            vis[v]=true;
            dfs(v,u);
        }
    }
}
int main()
{
    cin>>N;
    for(int i=0;i<N;i++)
    {
        int a,b;cin>>a>>b;
        a--,b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    for(int i=0;i<N;i++)
    {
        if(G[i].size()!=2)
        {
            cout<<-1<<endl;
            return 0;
        }
    }
    int cnt=N;
    for(int i=0;i<N;i++)
    {
        if(!vis[i])
        {
            cnt--;
            vis[i]=true;
            dfs(i,-1);
        }
    }
    cout<<cnt<<endl;
}



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

using namespace std;

int main(int argc, char *argv[]) {
    //
    //  ABピザを 2t 枚買ったとすると、Aピザt枚、Bピザt枚に分割される
    //  Aピザにかかるお金 A(X - t / 2) + tC
    //  Bピザにかかるお金 B(Y - t / 2) + tC
    //  但し、 t / 2 の方が X, Y より大きかった時は、t で全部賄うとする
    //

    int A, B, C, X, Y;
    cin >> A >> B >> C >> X >> Y;

    int ans = INT_MAX;

    //  AB ピザを t 枚買ったとする
    //  t は、0 から　max(X, Y) * 2 まで動く
    for (int t = 0; t <= max(X, Y) * 2; t++) {
        int cur_cost = A * max(X - t / 2, 0) + B * max(Y - t / 2, 0) + t * C;
        if (ans >= cur_cost) {
            ans = cur_cost;
        } 
    }
    cout << ans << endl;
    return 0;
}


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

const int N = 100010;
const int moder = 998244353;

int cnt[N], p[N];

int main(){
    int n;
    scanf("%d", &n);
    for (int i = 0, x; i < n; ++ i){
        scanf("%d", &p[i]);
        ++ cnt[p[i]];
    }
    if (cnt[0] != 1){
        puts("0");
        return 0;
    }
    if (p[0] != 0){
        puts("0");
        return 0;
    }
    int ans = 1;
    for (int i = 1; i < N - 1; ++ i){
        if (!cnt[i] && cnt[i + 1]){
            puts("0");
            return 0;
        }
        if (cnt[i - 1]){
            for (int j = 0; j < cnt[i]; ++ j){
                ans = 1ll * ans * cnt[i - 1] % moder;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 1024
package main

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

func main() {
  input := Input{bufio.NewReaderSize(os.Stdin,100000)}
  h,w := input.NextInts()
  var g [2002][2002]int
  for j:=0;j<w+2;j++ { g[0][j],g[h+1][j] = -1,-1 }
  for i:=1;i<h+1;i++ {
    s := input.NextLine()
    g[i][0],g[i][w+1] = -1,-1
    for j:=1;j<w+1;j++ {
      if s[j-1:j] == "#" { g[i][j] = -1 }
    }
  }
  for i:=1;i<h+1;i++ {
    l := 0
    for j:=1;j<w+2;j++ {
      if g[i][j] != -1 { continue }
      for k:=l+1;k<j;k++ { g[i][k] = j-l-1 }
      l = j
    }
  }
  for j:=1;j<w+1;j++ {
    u := 0
    for i:=1;i<h+2;i++ {
      if g[i][j] != -1 { continue }
      for k:=u+1;k<i;k++ { g[k][j] += i-u-2 }
      u = i
    }
  }
  m := -1
  for i:=1;i<h+1;i++ {
    for j:=1;j<w+1;j++ {
      if m < g[i][j] { m = g[i][j] }
    }
  }
  fmt.Println(m)
}

type Input struct { reader *bufio.Reader }
func(i *Input) NextLine() string {
  var buffer []byte
  for {
    line,isPrefix,err := i.reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer,line...)
    if !isPrefix { break }
  }
  return string(buffer)
}
func(i *Input) NextInts() (int,int) {
  s := strings.Split(i.NextLine()," ")
  x,_ := strconv.Atoi(s[0])
  y,_ := strconv.Atoi(s[1])
  return x,y
}

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

const int maxn = 2e5 + 10;
LL sum, ans;
int n;
map<LL, LL> cnt;

int main()
{
    scanf("%d", &n);
    cnt[0] ++;
    for(int i = 1; i <= n; i ++) {
        LL x;
        scanf("%lld", &x);
        sum += x;
        ans += cnt[sum];
        cnt[sum] ++;
    }
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 12800
def E(n):
    return n * (n + 1) // 2 / n


N, K = map(int, input().split())
P = list(map(int, input().split()))

tmp = sum(map(E, P[:K]))
res = tmp

for i in range(1, N - K + 1):
    tmp = tmp - E(P[i - 1]) + E(P[i + K - 1])
    res = max(res, tmp)

print(res)


Measured memory_bytes: 25604
#include<stdio.h>
int main()
{
	char name;
	scanf("%c", &name);
	
	if(name>='a' && name<='z'){
	
	printf("a\n");}
	else
	{
		if(name>='A' && name<='Z'){
		printf("A");}
	}
	
	
	
	
	return 0;
}

Measured memory_bytes: 1596
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <list>
#include <iomanip>
#include <queue>
#include <cmath>
#include <numeric>
#define repl(i, l, r) for (ll i = l; i < r; i++)
#define rep(i, n) repl(i, 0, n)

using namespace std;
using ll = long long;
typedef pair<ll, ll> P;
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; }
const long long mod = 1e9 + 7;
ll gcd(ll a, ll b);
ll lcm(ll a, ll b);
ll dx[] = { 1, 0 , -1,  0 }, dy[] = { 0, 1, 0, -1 };
ll cb(ll a, ll b);

int main() {
	ll h, w;
	cin >> h >> w;

	char s[60][60];
	ll dp[60][60];

	ll cnt = 0;

	rep(i, 60)rep(j, 60) s[i][j] = '-';
	rep(i, 60)rep(j, 60) dp[i][j] = mod;
	rep(i, h) {
		rep(j, w) {
			cin >> s[i + 1][j + 1];
			if (s[i + 1][j + 1] == '.') cnt++;
		}
	}

	ll ans;

	if (s[1][1] != s[h][w]) ans = -1;


	dp[1][1] = 0;

	queue<P> p;
	p.push(P(1, 1));
	
	while (p.size()) {
		ll i, j, np;
		i = p.front().first;
		j = p.front().second;
		p.pop();
		rep(k, 4) {
			np = dp[i][j] + 1;
			if (s[i + dx[k]][j + dy[k]] == '.') {
				if (np < dp[i + dx[k]][j + dy[k]]) {
					dp[i + dx[k]][j + dy[k]] = np;
					p.push(P(i + dx[k], j + dy[k]));
				}
			}
		}
	}

	if (dp[h][w] == mod) {
		cout << -1;
	}
	else {
		cout << cnt - dp[h][w] - 1;
	}

	return 0;
}


ll cb(ll a, ll b) {
	ll ans = 1;
	rep(i, b) ans *= (a - i);
	rep(i, b) ans /= (b - i);

	return ans;
}


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

int main(){
	int N; cin >> N;
	string s[N]; for (int i=0; i<N; i++) cin >> s[i];

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

	int ans = 0;
	for (int i=0; i<N; i++){
		int temp1 = 0;
		for (int j=0; j<N; j++){
			if (s[j] == s[i]){
				temp1++;
			}
		}
		for (int j=0; j<M; j++){
			if (t[j] == s[i]){
				temp1--;
			}
		}

		if (ans < temp1){
			ans = temp1;
		}

		// cout << "i = " << i << endl;
		// cout << "s[i] = " << s[i] << endl;
		// cout << "temp1: " << temp1 << endl << endl;
	}

	cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>

#define N 100

int min(int x,int y){
  if(x > y) return y;
  else return x;
}

int main()
{
  int n,i,p[N+1],m[N+1][N+1],l,j,k;
  scanf("%d",&n);
  for(i=1;i<=n;i++){
    scanf("%d%d",&p[i-1],&p[i]);
  }

  for(i=1;i<=n;i++) m[i][i] = 0;
  for(l=2;l<=n;l++){
    for(i=1;i<=n-l+1;i++){
      j = i + l - 1;
      m[i][j] = 10000000;
      for(k=i;k<=j-1;k++){
	m[i][j] = min(m[i][j],m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]);
      }
    }
  }

  printf("%d\n",m[1][n]);

  return 0;
}



Measured memory_bytes: 2056
import random
def tester(N=0):
	'''制約
1≦N≦105
1≦Ai≦109
'''
	maxno1=1e5
	maxno2=1e9
	s=input()
	if s!='':return(s)
	
	if N==0:
		return(random.randint(2,maxno1))
	else:
		print('Testing...')
		print('N=',N)
		A=[]
		for i in range(N):
			A.extend([random.randint(1,maxno2)])
		return(' '.join(list(map(str,A))))

import copy

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def gcdm(x):
	g=x[0]
	for i in range(1,len(x)):
		if g==1:
			return(g)
		g=gcd(g,x[i])
	return(g)

def playmove(A,i):
	A[i]-=1
	g=gcdm(A)
	return([x//g for x in A])

def noofevens(A):
	r=0
	for i in A:
		if i%2==0:
			r+=1
	return(r)
			

N=int(tester())
A=[int(x) for x in tester(N).split()]


isFirstmove=True
while True:
	e=noofevens(A)
	if e%2==1:
		if isFirstmove:
			print('First')
		else:
			print('Second')
		break
	elif N-e>1:
		if isFirstmove:
			print('Second')
		else:
			print('First')
		break
	else:	
		for i in range(N):
			if A[i]%2==1:
				break
		if A[i]==1:
			if isFirstmove:
				print('Second')
			else:
				print('First')
			break
		else:
			A=playmove(A,i)
			isFirstmove=(isFirstmove!=True)
		




	

Measured memory_bytes: 15888
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define REPL(i,m,n) for(ll i=(ll)(m); i<(ll)(n); i++)
#define repl(i,n) REPL(i,0,n)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;
int main() {
  int N, P;
  cin >> N >> P;
  vector<int> A(N);
  vector<int> cnt(2);
  rep(i, N) {
    cin >> A[i];
    cnt[A[i]%2]++;
  }
  if(cnt[1] == 0) {
    if(P) cout << 0 << endl;
    else cout << (ll)pow(2, N) << endl;
  } else {
    cout << (ll)pow(2, N-1) << endl;
  }
  return 0;
}


Measured memory_bytes: 640
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<algorithm>
using std::cout;
using std::cin;
using std::endl;
const long long INF=100000000000000000;

struct edge{
    int to;
    int cost;
};
typedef std::pair<long long,int> P;
int n,m,s,t;
std::vector<edge> G_y[100001];
std::vector<edge> G_s[100001];
long long cost_y[100001];
long long cost_s[100001];
std::priority_queue<P,std::vector<P>,std::greater<P> > que;
std::priority_queue<P,std::vector<P>,std::greater<P> > que2;

void debug(){
    cout<<"---dijkstra by yen---"<<endl;
    for(int i=0;i<=n;i++){
        cout<<i<<" "<<cost_y[i]<<endl;
    }
    cout<<"---dijkstra by snuuk---"<<endl;
    for(int i=0;i<=n;i++){
        cout<<i<<" "<<cost_s[i]<<endl;
    }
}

int main(void){
    cin>>n>>m>>s>>t;
    int m1,m2,m3,m4;
    edge me;
    for(int i=0;i<m;i++){
        scanf("%d%d%d%d",&m1,&m2,&m3,&m4);
        me.to=m2;
        me.cost=m3;
        G_y[m1].push_back(me);
        me.to=m1;
        G_y[m2].push_back(me);
        me.to=m2;
        me.cost=m4;
        G_s[m1].push_back(me);
        me.to=m1;
        G_s[m2].push_back(me);
    }
    for(int i=0;i<=n;i++){
        cost_y[i]=INF;
        cost_s[i]=INF;
    }

    //ダイクストラ
    cost_y[s]=0;
    que.push(std::make_pair(0,s));
    while(!que.empty()){
        P p=que.top(); que.pop();
        int v=p.second;
        if(cost_y[v]<p.first) continue;
        for(int i=0;i<G_y[v].size();i++){
            edge e=G_y[v][i];
            if(cost_y[e.to]>cost_y[v]+e.cost){
                cost_y[e.to]=cost_y[v]+e.cost;
                que.push(P(cost_y[e.to],e.to));
            }
        }
    }
    cost_s[t]=0;
    que2.push(std::make_pair(0,t));
    while(!que2.empty()){
        P p=que2.top(); que2.pop();
        int v=p.second;
        if(cost_s[v]<p.first) continue;
        for(int i=0;i<G_s[v].size();i++){
            edge e=G_s[v][i];
            if(cost_s[e.to]>cost_s[v]+e.cost){
                cost_s[e.to]=cost_s[v]+e.cost;
                que2.push(P(cost_s[e.to],e.to));
            }
        }
    }

    //debug();

    long long totalcost[100001];
    for(int i=0;i<=n;i++) totalcost[i]=INF;
    totalcost[n-1]=cost_y[n]+cost_s[n];

    long long tempcost;
    for(int i=n-2;i>=0;i--){
        tempcost=cost_y[i+1]+cost_s[i+1];
        if(totalcost[i+1]>tempcost){
            totalcost[i]=tempcost;
        }else{
            totalcost[i]=totalcost[i+1];
        }
    }

    for(int i=0;i<n;i++){
        cout<<1000000000000000-totalcost[i]<<endl;
    }

	
    return 0;
}


Measured memory_bytes: 17396
#include <cstdio>
#include <vector>
using namespace std;

int n;
int a[10];
vector<int> l, r;
vector<int> emp;

bool dfs(int p){
//	printf("p=%d\n", p);
	/*
	printf("l ");
	for(int i=0; i<l.size(); i++){
		printf("%d ", l[i]);
	}
	printf("\nr ");
	for(int i=0; i<r.size(); i++){
		printf("%d ", r[i]);
	}
	printf("\n");
*/
	if(p == 10) return true;
	l.push_back(a[p]);
	if(l.size() == 1 || l[l.size() - 2] < l[l.size() - 1]){
		return dfs(p+1);
	}else{
		l.pop_back();
		r.push_back(a[p]);
		if(r.size() == 1 || r[r.size() - 2] < r[r.size() - 1]){
			return dfs(p+1);
		}else{
			r.pop_back();
			return false;
		}
	}
}

int main(){
	scanf("%d", &n);
	for(int i=0; i<n; i++){
		l = emp;
		r = emp;
		for(int j=0; j<10; j++){
			scanf("%d", &a[j]);
		}
		if(dfs(0)) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

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



int main(){
	int n,a,cnt,MX=0,ans=1;
	cin >> n;
	for(int i=1;i<=n;i++){
		a=i;
		cnt=0;
		while(1){
			if(a%2) break;
			a/=2;
			cnt++;
		}
		if(MX<cnt){
			MX=cnt;
			ans=i;
		}
	}
	
	cout << ans << endl;
	return 0;
}

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

string X;
deque<char> dchar;

int main()
{
    cin>>X;

    for (int i=0; i<X.size(); i++)
    {
        dchar.push_back(X[i]);

        if (dchar.size()>=2 && dchar[dchar.size()-2]=='S' && dchar[dchar.size()-1]=='T')
        {
            dchar.pop_back();
            dchar.pop_back();
        }
    }

    cout<<dchar.size()<<endl;
}

Measured memory_bytes: 3704
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
B = Counter(list(i+1+A[i] for i in range(N)))
#print(B,B[3])
C = Counter((i+1-A[i] for i in range(N)))
ans = 0
#print(C)
for j in range(N):
    ans += B[j]*C[j]
print(ans)

Measured memory_bytes: 59520
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
#define rep(i,x) for(ll i = 0; i < (ll)(x); i++)
#define pb push_back
#define eb emplace_back
#define debug(x) cerr << #x << ": " << (x) << "\n";
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<vector<ll>>> vvvl;
const ll INF = numeric_limits<ll>::max()/4;
const ll MOD = 1e9+7;
const int n_max = 1e5+10;

int main(){
    ll n,a,b; cin >> n >> a >> b;
    ll min_ = a * (n-1) + b;
    ll max_ = a + b * (n-1);
    cout << max(max_ - min_ + 1, 0LL) << endl;
}

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

int n, m, s;

const int maxn = 105;
int a[maxn], b[maxn], c[maxn], d[maxn];
typedef long long ll;
ll dis[55][5500];
typedef pair<int, int> pi;
vector<pi> G[maxn];

void dij(){
    for(int i = 1;i <= n;i++){
        for(int j = 0;j <= 5000;j++){
            dis[i][j] = 1e18;
        }
    }
    dis[1][s] = 0;
    priority_queue<pair<ll, pi>, vector<pair<ll, pi> >, greater<pair<ll, pi> > > pq;
    pq.push(make_pair(0, make_pair(1, s)));
    while(!pq.empty()){
        pair<ll, pi> p = pq.top(); pq.pop();
        ll D = p.first;
        int u = p.second.first;
        int coins = p.second.second;
        int coins1 = min(coins + c[u], 5000);
        if(dis[u][coins] + d[u] < dis[u][coins1]){
            dis[u][coins1] = dis[u][coins] + d[u];
            pq.push(make_pair(dis[u][coins1], make_pair(u, coins1)));
        }
        for(auto edge : G[u]){
            int v = edge.first;
            int id = edge.second;
            if(coins >= a[id] and dis[v][coins - a[id]] > dis[u][coins] + b[id]){
                dis[v][coins - a[id]] = dis[u][coins] + b[id];
                pq.push(make_pair(dis[v][coins - a[id]], make_pair(v, coins - a[id])));
            }
        }
    }
    for(int i = 2;i <= n;i++){
        ll ans = 1e18;
        for(int j = 0;j <= 5000;j++){
            ans = min(ans, dis[i][j]);
        }
        cout << ans << endl;
    }
}


int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m >> s;
    s = min(s, 5000);
    for(int i = 1;i <= m;i++){
        int u, v;
        cin >> u >> v >> a[i] >> b[i];
        G[u].push_back({v, i});
        G[v].push_back({u, i});
    } 
    for(int i = 1;i <= n;i++){
        cin >> c[i] >> d[i];
    }
    dij();
    return 0;
}


Measured memory_bytes: 9432
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;
int N;
int A[105000];
int ans = -1;

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    for(int i = 1; i <= N; i++) {
        cin >> A[i];
        if(A[i] > A[i-1]) ans++;
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 3556
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, P> P3;
typedef pair<P ,P> PP;
constexpr ll MOD = ll(1e9) + 7;
constexpr int IINF = INT_MAX;
constexpr ll LLINF = LLONG_MAX;
constexpr int MAX_N = int(2e5) + 5;
constexpr double EPS = 1e-8;
constexpr int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define SORT(v) sort((v).begin(), (v).end())
#define SORTR(v) sort((v).rbegin(), (v).rend())
#define ALL(v) (v).begin(), (v).end()

struct edge{
    int to, cap, rev;
};

struct Flow{
    Flow(int n){
        G.resize(n);
    }
    vector<vector<edge> > G;
    vector<bool> used;
    
    void add_edge(int from, int to, int cap){
        G[from].emplace_back((edge){to, cap, int(G[to].size())});
        G[to].emplace_back((edge){from, 0, int(G[from].size())-1});
    }
    
    // 増加路の探索
    int dfs(int v, int t, int f){
        if(v == t) return f;
        used[v] = true;
        for(auto &e : G[v]){
            if(!used[e.to] && e.cap > 0){
                int d = dfs(e.to, t, min(f, e.cap));
                if(d > 0){
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    
    int max_flow(int s, int t){
        used.resize(G.size());
        int flow = 0;
        while(1){
            fill(used.begin(), used.end(), false);
            int f = dfs(s, t, IINF);
            if(f==0) break;
            flow += f;
        }
        return flow;
    }
};

int main() {
    int n, m, S, T, U, V;
    cin >> n >> m >> S >> T >> U >> V;
    S--; T--;
    U--; V--;
    Flow flow1(n+2);
    for(int i=0;i<m;i++){
        int u, v;
        cin >> u >> v;
        u--; v--;
        flow1.add_edge(u,v,1);
        flow1.add_edge(v,u,1);
    }
    int SS = n, TT = n+1;
    flow1.add_edge(SS, S, INT_MAX/2);
    flow1.add_edge(T, TT, INT_MAX/2);
    Flow flow2 = flow1;
    flow1.add_edge(SS, U, INT_MAX/2);
    flow1.add_edge(V, TT, INT_MAX/2);
    flow2.add_edge(SS, V, INT_MAX/2);
    flow2.add_edge(U, TT, INT_MAX/2);
    cout << min(flow1.max_flow(SS,TT), flow2.max_flow(SS,TT)) << endl;
    return 0;
}



Measured memory_bytes: 17664
#include<stdio.h>
#define max 100
#define White 0
#define Gray 1
#define Brack 2

int color[max],d[max],Dep[max][max]={0};
int tt,g[max];
int n;

void visit(int u){
  int i;
  color[u]=Gray;
  d[u] = ++tt;
  for(i=0;i<n;i++){
    if(Dep[u][i]==0)continue;
    if(color[i]==White){
      visit(i);
    }
  }
  color[u] = Brack;
  g[u]=++tt;
}

void dfs(){
  int i;
  for(i=0;i<n;i++){
    color[i]=White;
  }
  tt = 0;
  for(i=0;i<n;i++){
    if(color[i]==White)visit(i);
  }
  for(i=0;i<n;i++){
    printf("%d %d %d\n",i+1,d[i],g[i]);
  }
}

int main(){
  int u,k,num;
  int i,j;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d%d",&u,&k);
    u--;
    for(j=0;j<k;j++){
      scanf("%d",&num);
      num--;
      Dep[u][num]=1;
    }
  }
  dfs();
  return 0;
}
    



Measured memory_bytes: 2060
#![allow(
  non_snake_case,
  unused_variables,
  unused_assignments,
  unused_mut,
  unused_imports,
  unused_macros,
  dead_code
)]
use proconio::fastout;
use proconio::input;
use proconio::marker::*;
use std::cmp::*;
use std::collections::*;
//use std::collections::VecDeque;
macro_rules! debug {
  ($($a:expr),* $(,)*) => {
      #[cfg(debug_assertions)]
      eprintln!(concat!($("| ", stringify!($a), "={:?} "),*, "|"), $(&$a),*);
  };
}
#[fastout]
fn main() {
  input! {
    N:usize,
    XY:[(i64,i64);N]
  }
  // 傾き-1の線分の距離が最大になるケースと傾き1の線分のケースで考える。
  // 傾き1のケース
  let mut minV1 = 2000000000;
  let mut maxV1 = -2000000000;
  let mut minV2 = 2000000000;
  let mut maxV2 = -2000000000;
  for i in 0..N {
    let v1 = XY[i].0 + XY[i].1;
    let v2 = XY[i].0 - XY[i].1;
    minV1 = min(minV1, v1);
    minV2 = min(minV2, v2);
    maxV1 = max(maxV1, v1);
    maxV2 = max(maxV2, v2);
  }
  let mut ans = max(maxV1 - minV1, maxV2 - minV2);
  println!("{}", ans);
}


Measured memory_bytes: 8972
#include <algorithm>
#include <iostream>

using namespace std;
using ll = long long;
using ld = long double;

#define ALL(x) begin(x), end(x)
#define REP(i, n) for (size_t i = 0, i##_len = (n); i < i##_len; ++i)

void solve(string S) {
  cout << count(ALL(S),'1') << endl;
}

int main() {
  string S;
  cin >> S;
  solve(S);
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
 
using namespace std;
 
#define pb(n)	push_back(n)
#define mp(n,m) make_pair(n,m)
#define fi 	first
#define se 	second
#define all(r) r.begin(),r.end()

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const int IMAX=((1<<30)-1)*2+1;
const double EPS=1e-10;
//int mod=1000000007;



int main(){
	double xa1,ya1,xa2,ya2,xb1,yb1,xb2,yb2;
	while(cin>>xa1>>ya1>>xa2>>ya2>>xb1>>yb1>>xb2>>yb2){
		double c1x=(xa1+xa2)/2.0,c1y=(ya1+ya2)/2.0;
		double c2x=(xb1+xb2)/2.0,c2y=(yb1+yb2)/2.0;
		double r1x=fabs(xa1-c1x),r1y=fabs(ya1-c1y);
		double r2x=fabs(xb1-c2x),r2y=fabs(yb1-c2y);
		// c1x=fabs(c1x);
		// c1y=fabs(c1y);
		// c2x=fabs(c2x);
		// c2y=fabs(c2y);
		if((fabs(c1x-c2x)<=r1x+r2x+EPS)&&(fabs(c1y-c2y)<=r1y+r2y+EPS))cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
		//cout<<(r1x+r2x-fabs(c1x-c2x))<<" "<<(r1y+r2y-fabs(c1y-c2y))<<endl;
		// cout<<"c1("<<c1x<<","<<c1y<<") c2("<<c2x<<","<<c2y<<")"<<endl;
		// cout<<"r1("<<r1x<<","<<r1y<<") r2("<<r2x<<","<<r2y<<")"<<endl;
	}
}

Measured memory_bytes: 1216
#include<iostream>
#include<algorithm>
#include<functional>
#include<cstdint>
using namespace std; // 575

const int MAX = 100001;
int main() {
	int K, N;
	static pair<int, int> sushi[MAX];
	cin >> N >> K;
	for (int i = 0;i < N;++ i) cin >> sushi[i].second >> sushi[i].first;
	sort(sushi, sushi+N, greater<pair<int, int> >());
	static int eatSushi[MAX]; // eatSushi[i]は第i種類目の寿司の食べた個数
	for (int i = 0;i < N;++ i) eatSushi[i] = 0;
	
	int64_t delicious = 0, ans;
	int64_t kind = 0;
	for (int i = 0;i < K;++ i) { // まずまぁ美味しさ基礎だけK個上から
		delicious += sushi[i].first;
		if (!eatSushi[sushi[i].second]) ++ kind; // 種類数
		++ eatSushi[sushi[i].second];
	}
	ans = delicious + kind * kind;
	++ kind;
	for (int i = K - 1, j = K;kind <= K;++ kind, -- i, ++ j) { // iが取り除く寿司、jが増やす寿司
		while(j < N && eatSushi[sushi[j].second]) ++ j; // まだ食べてない種類の寿司へ
		if (j >= N) break; // ここで寿司の種類が尽きた
		while(eatSushi[sushi[i].second] <= 1) -- i; // 2種類以上ある寿司へ
		delicious += sushi[j].first - sushi[i].first; // 寿司交換
		++ eatSushi[sushi[j].second];
		-- eatSushi[sushi[i].second];
		ans = max(ans, delicious + kind * kind);
	}
	
	cout << ans;
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり
また、コンテスト後に https://31536000.hatenablog.com/ で解説していると思うので、良かったら読んでねー

まず、種類ボーナスが無ければ食べる寿司は自明です。
次に、食べる種類数を1個以上、種類ボーナスを1*1以上としてもまだ自明です。
次に、食べる種類数を2個以上、種類ボーナスを2*2以上とするとき、
K個が全て同じならばその中で一番美味しさが少なかった寿司(かつ2種類以上の奴)を、
その種類以外の中で最もおいしい寿司に取り換えるだけですね。
この試行を繰り返していけば、食べる種類数をK個にするまでO(NlogN+K)で求まりそうです(NlogNはソート)
で、実際にこれで求まるので終わり
*/

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

#define int             long long
#define FOR( i, m, n )  for( int (i) = (m); (i) < (n); (i)++ )
#define REP( i, n )     FOR( i, 0, n )
#define REPR( i, m )    for( int (i) = (m); (i) >= 0; (i)-- )
#define REPONE( i, n )  FOR( i, 1, n + 1 )
#define ALL( a )        (a).begin(), (a).end()
#define MP              make_pair

using namespace std;
using P = pair<int, int>;

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( a > b ) { a = b; return 1; } return 0; }

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

signed main(){
    int N; cin >> N;
    vector<string> s( N );
    REP( i, N ){
        cin >> s[i];
        sort( ALL( s[i] ) );
    }

    sort( ALL( s ) );

    int ans = 0, cnt = 0;
    REP( i, N - 1 ){
        if( s[i] == s[i + 1] ){
            cnt++;
        }
        if( s[i] != s[i + 1] || i == N -2 ){
            ans += cnt * ( cnt + 1 ) / 2;
            cnt = 0;
        }

    }

    cout << ans << endl;
}

Measured memory_bytes: 7296
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
#define REP(i,st,ed) for(int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(int i=st,i##end=ed;i>=i##end;--i)
const int maxn=2005,inf=0x3f3f3f3f;
bool a[maxn],b[maxn];
int n,l[maxn],r[maxn];
int c[maxn],cnt,Max[maxn],ans=inf;
char s[maxn];
bool cmp(const int &x,const int &y){
	return r[x]<r[y];
}
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	REP(i,1,n)a[i]=s[i]^48;
	scanf("%s",s+1);
	REP(i,1,n)b[i]=s[i]^48;
	bool flag=1;
	REP(i,1,n)flag&=(b[i]==0);
	if(flag){
		REP(i,1,n)flag&=a[i]==0;
		puts(flag?"0":"-1");
		return 0;
	}
	REP(i,1,n){
		l[i]=r[i]=inf;
		REP(j,1,n)
			if(b[j]){
				l[i]=min(l[i],(i-j+n)%n);
				r[i]=min(r[i],(j-i+n)%n);
			}
	}
	REP(i,1,n){
		int k=i;
		cnt=0;
		REP(j,1,n){
			if(b[j]!=a[k])
				c[++cnt]=k;
			k=k%n+1;
		}
		sort(c+1,c+1+cnt,cmp);
		Max[cnt+1]=0;
		DREP(j,cnt,1)
			Max[j]=max(Max[j+1],l[c[j]]);
		REP(j,0,cnt){
			ans=min(ans,cnt+2*(r[c[j]]+max((i-1+n)%n,Max[j+1]))-(i-1+n)%n);
			ans=min(ans,cnt+2*(Max[j+1]+max((1-i+n)%n,r[c[j]]))-(1-i+n)%n);
		}
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 384
T1, T2 = map(int,input().split())
A1, A2 = map(int,input().split())
B1, B2 = map(int,input().split())

A1 *= T1
B1 *= T1
A2 *= T2
B2 *= T2

if A1+A2 > B1+B2: # Aを遅く
    A1,B1 ,A2,B2 = B1,A1 ,B2,A2

if A1+A2 == B1+B2:
    print("infinity")
    exit()

if A1 < B1:
    print(0)
    exit()

def nibu(l,r):
    if l >= r:
        return l
    c = (l+r+1)//2
    if (A1+A2)*(c-1)+A1 >= (B1+B2)*(c-1)+B1:
        return nibu(c,r)
    else:
        return(nibu(l,c-1))

ans = nibu(0,10**100)
if (A1+A2)*(ans-1)+A1 == (B1+B2)*(ans-1)+B1:
    print(ans*2-2)
else:
    print(ans*2-1)

Measured memory_bytes: 3188
//-------All power is within you,you can do Anything and Everything.---------//
 
    #include <bits/stdc++.h>
    using namespace std;
  
//*$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ M $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$*//
 
    #define pb push_back
    #define MP make_pair
    #define F first
    #define S second
    #define sc(x) scanf("%lld",&x)
    #define pf(x) printf("%lld\n",x)
    #define int long long
    #define all(x) x.begin(),x.end() 
    #define fo(i,a,b) for(int i=a;i<b;i++)
    #define rfo(i,b,a) for(int i=b;i>=a;i--)
    #define mem( a, val ) memset(a, val, sizeof( a ) )
    #define deci( x ) cout<<fixed<<setprecision( x );
    #define bitcount( x ) __builtin_popcountll( x )
    #define endl "\n" 
    
    #define XOX 
    
    typedef vector<int> vi;
    typedef pair<int,int> pi; 
    
    const int MOD =  1000000007 ;
    const int MAX = 2e6 + 7;
    const int INF = 1e15;
    const int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
    const int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
    
//*$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ DEB $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$*//
    
    #define deb(x) cout<<#x<<" "<<x<<endl;


    vector<string> vec_splitter(string s) 
    {
        for(char& c: s) c = c == ','?  ' ': c;
        stringstream ss; ss << s;
        vector<string> res;
        for(string z; ss >> z; res.push_back(z));
        return res;
    }
    void debug_out(vector<string> args, int idx) { cerr << endl; }
    template <typename Head, typename... Tail>
    void debug_out(vector<string> args, int idx, Head H, Tail... T) 
    {
        if(idx > 0) cerr << ", ";
        stringstream ss; ss << H;
        cerr << args[idx] << " = " << ss.str();
        debug_out(args, idx + 1, T...);
    }
    
    #ifdef XOX
    #define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __VA_ARGS__)
    #else
    #define debug(...) 42
    #endif

//*$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ V $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$*//  
    
    int i,j,k,t,n,q,l,r,mid;

//*$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ F $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$*//
    
    queue<int> qq;
    int x;
    void solve()
    {
        cin>>k;
        fo(i,1,10)qq.push(i);
        k--;
        while(k--)
        {
            x=qq.front();
            // deb(x)   
            qq.pop();
            
            if(x%10!=0)
                qq.push((10*x)+(x%10)-1);
            
            qq.push((10*x)+(x%10));
            
            if(x%10!=9)
                qq.push((10*x)+(x%10)+1);
        }
        cout<<qq.front()<<endl;
        
    }
    
//*$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$*//
//                          GAME STARTS FROM HERE                            //
 
    int32_t main() 
    {
    
        // int start,stop=clock();
        // cout<<"time:"<<(stop-start)/double(CLOCKS_PER_SEC)*1000<<endl;
        ios_base::sync_with_stdio(0);
        cin.tie(NULL);

        // sc(t);while(t--)
        // cin>>t;while(t--)
            solve();
    
        return 0;
    }

Measured memory_bytes: 1792
#include <iostream>
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;

int main() {
    int n, m, x;
    int a[100];
    int k = 0, l = 0;
    cin >> n >> m >> x;
    rep(i, m) {
        cin >> a[i];
    }
    rep(i, m) {
        if (0 < a[i] && a[i] < x) {
            k++;
        } else if (x < a[i] && a[i] < n) {
            l++;
        }
    }
    cout << min(k, l) << endl;
    return 0;
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
sum = 0
for i in range(len(a)):
  sum += b[a[i]-1]
  if i>0:
    if a[i]-1 == a[i-1]:
      sum += c[a[i-1]-1]
print(sum)

Measured memory_bytes: 9152
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
int n,a,t;
double difftemp(int x){
    double r = double(t) - double(x) * 0.006;
    return abs(a-r);
}

int main(){
    cin >> n >> t >> a;
    vector<int> h(n);
    int ans = 0;
    double mindiff = 10000.0;
    for(int i=0;i<n;i++){
        cin >> h[i];
    }
    for(int i=0;i<n;i++){
        if(mindiff > difftemp(h[i])){
            ans = i+1;
            mindiff = difftemp(h[i]);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
N, M = map(int, input().split(' '))
L_list=[]
R_list=[]

for i in range(M):
    l,r = map(int, input().split(' '))
    L_list.append(l)
    R_list.append(r)

L_list.sort(reverse=True)
R_list.sort()
MAX = L_list[0]
MIN = R_list[0]
cnt=0
for i in range(1,N+1):
    if(i<=MIN and i>=MAX):
        cnt+=1
print(cnt)

Measured memory_bytes: 11420
#include <stdio.h>
#include<math.h>

#define N 10000

main(){
  
  int n,array[N],i,j,x=0,y=0;
  
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&array[i]);
  }
  
  for(i=0;i<n;i++){
    if(array[i]==1)   y=1;
    else if(array[i]==2)   y=0;
    else if(array[i]%2==0)  y=1;
    
    for(j=3;j<=sqrt(array[i]);j+=2){
      if(array[i]%j==0)    y=1;
    }
    if(y==0)  x++; 
      y=0;
  
  }   
    printf("%d\n",x);
    return 0;
  }

Measured memory_bytes: 632
#include<iostream>
using namespace std;
typedef long long int llint;
int main() {
	llint n, m;
	cin >> n >> m;
	if (n >= m / 2) {
		cout << m / 2 << endl;
	}
	else {
		llint x = n;
		m -= n * 2;
		cout << m / 4 + x << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<numeric>
#include<queue>
#include<stack>
#include<cstring>
#include<limits>
#include<functional>
#include<unordered_set>
#include<iomanip>
#include<cassert>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define pb push_back
#define eb emplace_back
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 50;
 
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;
}
using namespace std;

void solve(){
    string s;
    cin>>s;
    if(s=="SAT")cout<<1<<"\n";
    else if(s=="FRI")cout<<2<<"\n";
    else if(s=="THU")cout<<3<<"\n";
    else if(s=="WED")cout<<4<<"\n";
    else if(s=="TUE")cout<<5<<"\n";
    else if(s=="MON")cout<<6<<"\n";
    else cout<<7<<"\n";
}
 
signed main(){
	ios::sync_with_stdio(false);
    cin.tie(0);
	cout<<fixed<<setprecision(15);
	solve();
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <set>
#include <sstream>
#include <numeric>
#include <bitset>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cctype>
#include <cassert>
using namespace std;

typedef long long ll;
static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
bool ISINT(double x){return fabs(x-(int)x)<EPS;}
bool ISEQ(double x,double y){return fabs(x-y)<EPS;}
string itos(ll x){stringstream ss;ss<<x;return ss.str();}
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define EREP(i,a,b) for(int i=a;i<=b;i++)
#define erep(i,n) EREP(i,0,n)
#define foreach(itr,c) for(__typeof(c.begin()) itr=c.begin();itr!=c.end();itr++)

#define MAX_V 302
#define INF 999999999

class Edge{
public:
  int to,cap,rev;
  Edge(){}
  Edge(int _to,int _cap,int _rev){
    to = _to;
    cap = _cap;
    rev = _rev;
  }
};

int n,m;
int id[302][302];
vector<Edge> G[MAX_V];
set<int> ans;

void add_edge(int from,int to,int cap){
  G[from].push_back(Edge(to,cap,G[to].size()));
  G[to].push_back(Edge(from,0,G[from].size()-1));
}

int dfs(int v,int t,int f,bool *used){
  if(v == t) return f;
  used[v] = true;
  rep(i,G[v].size()){
    Edge &e = G[v][i];
    if(!used[e.to] && e.cap > 0){
      int d = dfs(e.to,t,min(f,e.cap),used);
      if(d > 0){
        if(id[v][e.to] == -1){
          ans.insert(id[e.to][v]);
        }

        e.cap -= d;
        G[e.to][e.rev].cap += d;
        return d;
      }
    }
  }
  return 0;
}

int max_flow(int s,int t){
  int flow = 0;
  while(1){
    bool used[MAX_V];
    memset(used,0,sizeof(used));
    int f = dfs(s,t,INF,used);
    if(f == 0) return flow;
    flow += f;
  }
}

int main(void){
  while(cin>>n>>m){
    memset(id,-1,sizeof(id));
    rep(i,MAX_V) G[i].clear();
    rep(i,m){
      int a,b;
      cin>>a>>b;
      add_edge(a,b,1);
      add_edge(b,a,1);
      id[a][b] = i+1;
    }
    int s,t;
    cin>>s>>t;
    ans.clear();
    cout<<max_flow(s,t)<<endl;
    cout<<ans.size()<<endl;
    foreach(i,ans){
      cout<<(*i)<<endl;
    }
  }
}

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

using ll = long long;
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) {
    cin >> a[i];
  }
  ll x = 1000;
  rep(i, n -1) {
    int s = a[i];
    int t = a[i + 1];
    if (s < t) {
      ll k = x / s;
      x %= s;
      x += k * t;
    }
  }
  cout << x << endl;
  return 0;
}

Measured memory_bytes: 3580
"""C."""

import sys

input = sys.stdin.readline  # noqa: A001

n = int(input())
a = list(map(int, input()[:-1].split(' ')))

MOD_VALUE = 10**9 + 7
result = 0

a_sum = sum(a)

for i, v in enumerate(a):
    result += v * (a_sum - v)
    a_sum -= v

if result < MOD_VALUE:
    print(result)
else:
    print(result % MOD_VALUE)


Measured memory_bytes: 31592
#include <stdio.h>
int main()
{
    int a,b;

    scanf("%d%d",&a,&b);

    if(a>=0 && b<=100)
    {
        int x=3*a+b;
        if(x<2)
        {
            printf("0\n");
        }
        else
        {
            printf("%d\n",x/2);
        }
    }
    return 0;
}


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

int n;
vector<long long int> t;

long long int gcd(long long int a, long long int b) {
    if (a < b) return gcd(b, a);
    while(b!=0){
        long long int r = a%b;
        a = b;
        b = r;
    }
    return a; 
}

long long int lcm(long long int a, long long int b) {
	long long int r = gcd(a, b);
	return a * (b/r);
}

int main() {
	cin >> n;
	t.resize(n);
	for (int i = 0; i < n; ++i) cin >> t.at(i);

	long long int l = t.at(0);

	for (int i = 1; i < n; ++i)
	{
		l = lcm(l, t.at(i));
	}

	cout << l << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using P = pair<ll,ll>;
const ll mod = 1e9+7;
#define ALL(x) (x).begin(),(x).end()
#define pow(x,y) modpow(x,y)
#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define REPS(i,n) for(ll (i)=1;(i)<=(n);(i)++)
#define RREP(i,n) for(ll (i)=(n-1);(i)>=0;(i)--)
#define RREPS(i,n) for(ll (i)=(n);(i)>0;(i)--)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());

template <class T = int>T in(){
    T x;
    cin >> x;
    return (x);
}

template<class T> inline void chmin(T& a, T b){
    if (a > b){
        a = b;
    }
}

template<class T> inline void chmax(T& a, T b){
    if (a < b){
        a = b;
    }
}

vector<bool> seen;
vector<ll> dist;
void dfs(const vector<vector<pair<int,int>>> &G,int v){
    seen[v] = true;
    REP(i,G[v].size()){
        if(seen[G[v][i].F])continue;
        dist[G[v][i].F] = (dist[v] + G[v][i].S)%2;
        dfs(G,G[v][i].F);
    }
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(10);
    int N = in();
    vector<vector<pair<int,int>>> graph(N);
    REP(i,N-1){
        int as = in()-1,asd = in()-1,asdf = in();
        graph[as].pb(mp(asd,asdf));
        graph[asd].pb(mp(as,asdf));
    }
    seen.assign(N,false);
    dist.assign(N,10000);
    dist[0] = 0;
    dfs(graph,0);
    REP(i,N)cout << dist[i] << "\n";
}

Measured memory_bytes: 8576
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using VI = vector<int>;
using VL = vector<ll>;
using VS = vector<string>;
template<class T> using PQ = priority_queue<T, vector<T>, greater<T>>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);++(i))
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);++(i))
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);--(i))
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);--(i))
#define each(i, a) for(auto &i : a)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
#define out(y,x) ((y) < 0 || h <= (y) || (x) < 0 || w <= (x))
#define line cout << "-----------------------------\n" 
#define ENDL(i,n) ((i) == (n) - 1 ? "\n" : " ")
#define stop system("pause")
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
constexpr ld eps = 1e-10;
constexpr ld pi = 3.1415926535897932;
template<class T>inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; }return false; }
template<class T>inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; }return false; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& is, vector<T>& v) { for (auto& elemnt : v)is >> elemnt; return is; }
template<class T>inline istream& operator>>(istream& is, deque<T>& v) { for (auto& elemnt : v)is >> elemnt; return is; }
template<class T, class U>inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template<class T>inline vector<T> vec(size_t a) { return vector<T>(a); }
template<class T>inline vector<T> defvec(T def, size_t a) { return vector<T>(a, def); }
template<class T, class... Ts>inline auto vec(size_t a, Ts... ts) { return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...)); }
template<class T, class... Ts>inline auto defvec(T def, size_t a, Ts... ts) { return vector<decltype(defvec<T>(def, ts...))>(a, defvec<T>(def, ts...)); }

class unionfind {
    VI par, rank;
    int forest_num;
public:
    unionfind(const int& n) : par(n), rank(n, 1), forest_num(n) {
        FOR(i, 0, n)par[i] = i;
    }
    int root(int x) {
        if (par[x] == x)return x;
        return par[x] = root(par[x]);
    }
    int size(int x) {
        if (par[x] == x)return rank[x];
        return size(par[x]);
    }
    void unite(int x, int y) {
        int rx = root(x), ry = root(y);
        if (rx == ry)return;
        if (rank[rx] < rank[ry]) {
            par[rx] = ry;
            rank[ry] += rank[rx];
        }
        else {
            par[ry] = rx;
            rank[rx] += rank[ry];
        }
        --forest_num;
    }
    bool same(int x, int y) { return root(x) == root(y); }
    int fnum() { return forest_num; }
};
int main() {
    init();

    int n, m; cin >> n >> m;
    unionfind uf(n);
    FOR(i, 0, m) {
        int x, y, z; cin >> x >> y >> z;
        uf.unite(x - 1, y - 1);
    }
    cout << uf.fnum() << "\n";
}

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

int main() {
	ll N;
	cin >> N;

	if (N % 2 == 1) {
		cout << 0 << endl;
		return 0;
	}
	else {
		N /= 2;
		ll ans = 0;
		ll q = 5;
		bool valid = true;
		while (valid) {
			ll Q = N / q;
			if (Q > 0) {
				ans += Q;
				q *= 5;
			}
			else {
				valid = false;
			}
		}
		cout << ans << endl;
	}

}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main() {
    long long N, K, i, t, a, b;
    long long arr[100001] = {0};
    cin >> N >> K;
    for(i = 0; i < N; i++) {
        cin >> a >> b;
        arr[a] += b;
    }
    for(i = 1, t = 0; i <= 100001; i++) {
        t += arr[i];
        if(t >= K) {cout << i; break;}
    }
}

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <map>
#include <utility>
#include <vector>
#include <cstdio>
#include <iomanip>
#include <cmath>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep1(i, n) for(int i = 1; i <= n; i++) 



int main() {
    int N, M, A[110];
    cin >> N >> M;

    rep(i,N) cin >> A[i];
    int all = 0;
    rep(i,N) {
        all += A[i];
    }

    double judge = (double)(all/4.0/M);
    int cnt = 0;
    rep(i,N) {
        if (A[i] >= judge) ++cnt;
    }

    if (cnt >= M) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

//Prime Quadruplet
public class Main{

	public static void main(String[] args) {
		int N = 10000000;
		boolean[] p = new boolean[N];
		Arrays.fill(p, true);
		p[0]=p[1]=false;
		for(int i=2;i<N;i++)if(p[i])for(int j=i*2;j<N;j+=i)p[j]=false;
		int[] q = new int[900];
		int id = 0;
		for(int i=13;i<N;i+=2){
			if(p[i-8]&&p[i-6]&&p[i-2]&&p[i]){
				q[id++]=i;
			}
		}
		Scanner sc = new Scanner(System.in);
		while(true){
			int n = sc.nextInt();
			if(n==0)break;
			int k = 0;
			while(k<id){
				if(q[k]>n)break;
				k++;
			}
			System.out.println(q[k-1]);
		}
	}
}

Measured memory_bytes: 22000
N, K = map(int, input().split())
nums = list(map(int, input().split()))

sum_num = sum(nums[:K])
max_num = sum_num

for i in range(1, N - K + 1):
  sum_num = sum_num - nums[i - 1] + nums[i + K - 1]
  if sum_num > max_num:
    max_num = sum_num
    
print((max_num + K) / 2)
    
    

Measured memory_bytes: 98984
a,b=gets.split(" ").map(&:to_i) ## 1 2を打つ
#puts a 　中身は2
#puts b   中身は3
$str = []
a.times do |s|
  key = gets.chomp
  $str[s] = key
end
b = b + 2
b.times{ print("#") }
puts("")
a.times do |i|
  print ("#")
  print $str[i]
  print ("#\n")
end
b.times{
  print("#")
}


Measured memory_bytes: 1788
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

int main(void){
  int A, B;
  cin >> A >> B;
  int ans = 0;
  if(A >= 13){
    ans = B;
  }else if(A >= 6){
    ans = B/2;
  }else{
    ans = 0;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256