akhauriyash/Code-Regression huggingface dataset:
Res = [[0,0,0,0],[0,0,0,0]]
while True:
    try:
        l,r = map(float,input().split())
        if l < 0.2:
            Res[0][3] += 1
        elif l < 0.6:
            Res[0][2] += 1
        elif l < 1.1:
            Res[0][1] += 1
        else:
            Res[0][0] += 1

        if r < 0.2:
            Res[1][3] += 1
        elif r < 0.6:
            Res[1][2] += 1
        elif r < 1.1:
            Res[1][1] += 1
        else:
            Res[1][0] += 1
    except:
        for i in range(4):
            ans = str(Res[0][i]) + " " + str(Res[1][i])
            print(ans)
        break

Measured memory_bytes: 7400
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
	
	
	
	public class Main {
	
		public static void main(String[] args) {
		
			Scanner sc = new Scanner(System.in);
			int n = sc.nextInt();	
			int k = sc.nextInt();
			
		    double p[] = new double[n];
			double ep[] = new double[n];
			double sumep[] = new double[n];
			List<Double>  ksumep = new ArrayList<>();
			
			for(int i=0;i<n;i++) {
				p[i] = sc.nextDouble();
			}
			
			for(int i=0;i<n;i++) {
				ep[i] = (1.0+p[i])/2.0;
			}
			
			for(int i=0;i<n;i++) {
				if(i==0) {
					sumep[i]=ep[i];
				}else {
					sumep[i]=sumep[i-1] + ep[i];
				}
			}
			
			for(int i=0;i<=n-k;i++) {
				if(i==0) {
					ksumep.add(sumep[k-1]) ;
				}else {
					ksumep.add(sumep[i+k-1]-sumep[i-1]) ;
				}
			}
			
			Collections.sort(ksumep,Collections.reverseOrder());
			
			System.out.println(ksumep.get(0));
		}
				
	}

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

int main() {
  int n;
  cin >> n;
  long double a[n];
  long double sum1=0.0,sum2=0.0;
  for (int i=0;i<n;i++){
    cin >> a[i];
    sum1 = sum1 + 1.0 / a[i];

  }
  sum2 = 1 / sum1;
  cout << sum2<<endl;
}

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


 int main()
 {
 	int a,b,c,d;
 	scanf("%d", &a);
	b=a/3600;
	c=a%3600/60;
	d=a%60;
 	printf("%d:%d:%d\n",b,c ,d);
 	
	

 	return 0;
 }


Measured memory_bytes: 2748
#include <bits/stdc++.h> 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define cout(x) cout<<x<<endl
#define all(v) v.begin(), v.end()
using namespace std;
//型エイリアス
using vi = vector<int>;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;
const ll inf = 1e18;
const int N = 2e5 + 10;


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

    int l = (int)s.size();
    while(l != 0){
        s.pop_back();
        s.pop_back();
        l = (int)s.size();
        string front = s.substr(0,l/2);
        string back = s.substr(l/2,l/2);
        if(front==back){
            cout(l);
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
N = int(input())
nes = [0] * N
for i in range(N) :
    li = input().split()
    li.append(i+1)
    li[1] = "-" + li[1]
    nes[i] = li
for i in range(N) :
    nes[i][1] = int(nes[i][1])
nes.sort()
for i in range(N) :
    print(nes[i][2])

Measured memory_bytes: 3064
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log2
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
O = list(input())
E = list(input())

ans = []

while E != []:
	ans.append(O.pop(0))
	ans.append(E.pop(0))

if O != []:
	ans.append(O.pop(0))

print("".join(ans))

Measured memory_bytes: 13664
import sys


n = int(input())
d = list(int(x) for x in input().split())

if d[0] != 0:
    print(0)
    sys.exit()
d.sort()
ans = 1
key = 1
value = 1
for i in range(1, n):
    if i == 1 and d[i] != 1:
        print(0)
        sys.exit()
    else:
        pass
    if d[i] == d[i-1]:
        key += 1
    else:
        if d[i] == d[i-1] + 1:
            if d[i-1] == 1:
                value = key
                key = 1
            else:
                ans *= pow(value, key)%998244353
                value = key
                key = 1
        else:
            print(0)
            sys.exit()
t = pow(value, key)
ans = ans*t%998244353
print(ans)


Measured memory_bytes: 14396
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
//template<typename key, typename val>
//using ordered_tree =
//  tree<key, val, std::less<>, rb_tree_tag, tree_order_statistics_node_update>;
using namespace std;
typedef long long int64;
typedef complex<double> comp;
const double pi = 3.14159265358979323846;
const int inf = (int)1e+9 + 2;
const int64 inf64 = (int64)1e+18 + 2;
const double dinf = 1e+20;
const int mod = 1'000'000'007;//*/998244353;
const int base = 2187;
const double eps = 1e-8;
const int N = 100'000;
const int LOGN = 19;

int n, m, k;

void solve(int test) {
  int a, b, c, d;
  cin >> a >> b >> c >> d; 
  cout << static_cast<int>(a + 1 == c && d == 1) << '\n';
}

void precalc() {
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  precalc();
  int test = 1;
  //cin >> test;
  //auto start = chrono::high_resolution_clock::now();
  for (int i = 1; i <= test; ++i) {
    solve(i);
  }
  //cerr << chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - start).count() << '\n';
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <tuple>
#include <vector>
#include <unordered_map>

std::vector<int> ans;
std::unordered_map<int, std::vector<std::tuple<int, int>>> t_map;

void dfs(int current, int parent, int parent_color, int w){
  ans[current] = w&1?1-parent_color:parent_color;
  for(const auto& it: t_map[current]){
    if(std::get<0>(it) == parent) continue;
    dfs(std::get<0>(it), current, ans[current], std::get<1>(it));
  }
}

int main(){
  int N;
  std::cin >> N;

  ans.resize(N+1);

  for(int i = 0; i < N; i++){
    int u,v,w;
    std::cin >> u >> v >> w;
    t_map[u].push_back(std::make_tuple(v,w));
    t_map[v].push_back(std::make_tuple(u,w));
  }

  dfs(1, -1, 0, 0);

  for(int i = 1; i < N+1; i++){
    std::cout << ans[i] << "\n";
  }

  return 0;
}



Measured memory_bytes: 11300
#include <iostream>
#include <algorithm>
using namespace std;
#define INF (ll)1e18

typedef long long ll;
ll N, A, B, h[100005];

int solve(ll k) {
    ll i, ex = 0;
    for (i = 0; i < N; i++) {
        ll t = h[i]-k*B;
        ll diff = (t+A-B-1)/(A-B);
        if (diff > 0) ex += diff;
    }
    return (ex <= k);
}

int main() {
    ll i, lo = 0, hi = 0, r = INF;
    cin >> N >> A >> B;
    for (i = 0; i < N; i++) {
        cin >> h[i];
        hi = max(hi, (h[i]+B-1)/B);
    }

    while (lo <= hi) {
        ll mid = lo + (hi-lo)/2;
        if (solve(mid)) {
            r = min(r, mid);
            hi = mid-1;
        } else {
            lo = mid+1;
        }
    }
    cout << r << '\n';
}

Measured memory_bytes: 1024
n=int(input())
x=list(map(int,input().split()))

min_i=[x[0]]
for i in range(1,n):
  min_i.append(min(min_i[i-1],x[i]))
  
count=0
for i in range(1,n):
  if min_i[i-1]<x[i]:
    count=count+1
    
print(n-count)

Measured memory_bytes: 24744
#include <stdio.h>
int main(){
	int a,b,d,r;
	double f;
	scanf("%d %d",&a,&b);
		d=a/b;
		r=a%b;
	f=(double)a/b;
	printf("%d %d %lf\n",d,r,f);
	return 0 ;
}

Measured memory_bytes: 2740
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = (1e9);

int main(){
  int N, K;
  cin >> N >> K;
  vector<int> P, M;
  for(int i = 0; i < N; ++i){
    int x;
    cin >> x;
    if(x >= 0) P.push_back(x);
    else M.push_back(x);
  }
  reverse(M.begin(), M.end());
  int ans = INF;
  if((int)P.size() >= K) ans = min(ans, P[K-1]);
  if((int)M.size() >= K) ans = min(ans, -M[K-1]);
  for(int i = 0; i < (int)P.size(); ++i){
    if(K-2-i >= 0 && K-2-i < (int)M.size())
      ans = min(ans, 2*P[i] - M[K-2-i]);
  }
  for(int i = 0; i < (int)M.size(); ++i){
    if(K-2-i >= 0 && K-2-i < (int)P.size())
    ans = min(ans, -2*M[i] + P[K-2-i]);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1020
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<vector>
#include<queue>
#include<map>
#include<set>

using namespace std;

#define int long long


signed main() {
	int n;
	cin >> n;

		vector<int> a(n + 1), b(n);

		for (int i = 0; i < n + 1; i++) {
			cin >> a[i];
		}
		for (int i = 0; i < n; i++) {
			cin >> b[i];
		}

		int ans = 0;
		//1村での処理
		//モンスター＞勇者の許容量なら
		if (a[0] <= b[0]) {
			ans += a[0];
			//勇者の許容量を減らす
			b[0] -= a[0];
		}
		//モンスター＜勇者の許容量なら
		else {
			ans += b[0];
			//勇者の許容量を次に引き継がせない
			b[0] = 0;
		}
		
		//2～n村目の処理
		for (int i = 1; i < n; i++) {
			//モンスター＜i-1とiの勇者の許容量のときモンスター数を答えに足す
			if (a[i] <= b[i] + b[i - 1]) {
				ans += a[i];
				//モンスター数がi-1番目の勇者が倒しきれないときi番目の勇者の許容量を減らす
				if (a[i] >= b[i - 1]) {
					b[i] = b[i] - a[i] + b[i - 1];
				}
			}
			//モンスター＞i-1とi番目の勇者の時勇者の許容量を足す
			else {
				ans += b[i] + b[i - 1];
				b[i] = 0;
			}
		}

		//n+1村の処理
		if (a[n] <= b[n - 1]) {
			ans += a[n];
		}
		else {
			ans += b[n - 1];
		}
		cout << ans;

	return 0;
}

Measured memory_bytes: 1792
#include <iostream>

using namespace std;

int main(){
  int N, T, A, X;
  cin >> N >> T >> A;
  int res = 0;
  int cc = 1<<30;
  for(int i=1;i<=N;i++){
    cin >> X;
    int d = (T*1000-X*6)-A*1000;
    if(d<0){
      d = -d;
    }
    if(cc>d){
      cc = d;
      res = i;
    }
  }
  cout << res << endl;
}

Measured memory_bytes: 256
import java.util.*;

class Main{
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		long min = 1000000, max = -1000000, sum = 0;
		
		int n = sc.nextInt();
		
		for(int i = 0; i < n; i++){
			long a = sc.nextInt();
			sum += a;
			min = Math.min(a, min);
			max = Math.max(a, max);
		}
		
		System.out.println(min + " " + max + " " + sum);
	}
}

Measured memory_bytes: 40628
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace Tasks
{
    public class C
    {
        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            Solve();
            Console.Out.Flush();
        }

        public static void Solve()
        {
            var (X, K, D) = Scanner.Scan<long, long, long>();
            var tmp = Math.Min(K, Math.Abs(X) / D);
            if (X >= 0)
            {
                X -= tmp * D;
            }
            else
            {
                X += tmp * D;
            }
            K -= tmp;


            Console.WriteLine(K % 2 == 0 ? Math.Abs(X) : Math.Min(Math.Abs(X + D), Math.Abs(X - D)));
        }

        public static class Scanner
        {
            private static Queue<string> queue = new Queue<string>();
            public static T Next<T>()
            {
                if (!queue.Any()) foreach (var item in Console.ReadLine().Trim().Split(" ")) queue.Enqueue(item);
                return (T)Convert.ChangeType(queue.Dequeue(), typeof(T));
            }
            public static T Scan<T>() => Next<T>();
            public static (T1, T2) Scan<T1, T2>() => (Next<T1>(), Next<T2>());
            public static (T1, T2, T3) Scan<T1, T2, T3>() => (Next<T1>(), Next<T2>(), Next<T3>());
            public static (T1, T2, T3, T4) Scan<T1, T2, T3, T4>() => (Next<T1>(), Next<T2>(), Next<T3>(), Next<T4>());
            public static (T1, T2, T3, T4, T5) Scan<T1, T2, T3, T4, T5>() => (Next<T1>(), Next<T2>(), Next<T3>(), Next<T4>(), Next<T5>());
        }
    }
}


Measured memory_bytes: 28356
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define N 100000
#define INF 100000000
typedef long long ll;
#define ALL(v) (v).begin(),(v).end()
#define SZ(x) int(x.size())
#define IN(a) cin>>(a)
#define OUT(a) cout<<(a)<<endl
typedef pair<int,int> P;
const int MAX = 100005;
const int MOD = 1000000007;
int main(){
    int a,b;
    cin>>a>>b;
    if(a<=5)b=0;
    else if(a>5&&13>a)b/=2;
    OUT(b);
    return 0;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int k = Integer.parseInt(sc.next());
        
        int[] v = new int[n];
        for(int i=0;i<n;i++){
            v[i] = Integer.parseInt(sc.next());
        }
        sc.close();
        int max = 0;
        int A,B;
        int count = Math.min(n,k);
        List<Integer> jewel = new ArrayList<Integer>();
        int sum = 0;
        for(A=0;A<=count;A++){
            for(B=0;A+B<=count;B++){
                sum = 0;
                jewel.clear();
                for(int i=0;i<A;i++){
                    sum+=v[i];
                    jewel.add(v[i]);
                }
                for(int i=n-B;i<n;i++){
                    sum+=v[i];
                    jewel.add(v[i]);
                }
                Collections.sort(jewel);
                int idx = 0;
                while(idx < jewel.size() && idx<k-A-B && jewel.get(idx)<0 ){
                    sum-=jewel.get(idx++);
                }
                max = Math.max(sum,max);
            }
        }
        System.out.println(max);

    }
}

Measured memory_bytes: 22228
//header{{{
#include<bits/stdc++.h>
  
using namespace std;
 
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define setout(n,x) setw(n+1) << setfill(x)
#define Fixed fixed << setprecision(10)
#define int int64_t
using pii = pair<int,int>;
constexpr int INF  = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod = 1e9+7; 

template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class T> using max_heap = priority_queue<T>;
  
int gcd(int a,int b){ return b ? gcd(b,a % b) : a;}
int lcm(int a,int b){ return a / gcd(a,b) * b;}
//}}}
int n,q;
vector<vector<int> > graph;
vector<int> node;
vector<bool> visited;

void dfs(int now){
	visited[now] = true;
	rep(i,graph[now].size()){
		int next = graph[now][i];
		if(!visited[next]){
			node[next] += node[now];
			dfs(next);
		}
	}
	return;
}


signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n >> q;
	graph.resize(n+1);
	node.resize(n+1);
	visited.resize(n+1);
	rep(i,n-1){
		int a,b;
		cin >> a >> b;
		graph[a].emplace_back(b);
		graph[b].emplace_back(a);
	}
	rep(i,q){
		int p,x;
		cin >> p >> x;
		node[p] += x;
	}

	dfs(1);

	reps(i,n){
		cout << (i == 1 ? "" : " ") << node[i];
	}
	cout << '\n';

	return 0;
}


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

int main(){
    int N;
    cin >> N;
    vector<int> A_count(N, 0);
    for(int i=0;i<N;i++){
        int A;
        cin >> A;
        A_count[A]++;
    }
    if(N % 2 == 1 && A_count[0] != 1){
        cout << 0 << endl;
        return 0;
    }
    ll ans = 1;
    for(int i=1;i<N;i++){
        if(N % 2 == 0){
            if(i % 2 == 0){
                if(A_count[i] != 0){
                    cout << 0 << endl;
                    return 0;
                }
            }else{
                if(A_count[i] != 2){
                    cout << 0 << endl;
                    return 0;
                }
                ans = (2 * ans) % MOD;
            }
        }else{
            if(i % 2 == 0){
                if(A_count[i] != 2){
                    cout << 0 << endl;
                    return 0;
                }
                ans = (2 * ans) % MOD;
            }else{
                if(A_count[i] != 0){
                    cout << 0 << endl;
                    return 0;
                }
            }
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 640
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <algorithm>
#include <limits.h>
#include <cmath>
#include <time.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define SQR(X) ((X)*(X))
int test = 0;
/* ここからが本編 */
int main(void)
{
  int i,j,k,l;
  int rep = 100000;
  int n;
  cin >> n;
  rep(i,n) {
    ull a = rep;
    rep += rep*5/100/1000*1000;
    if( (a*5) % (1000*100)) {
      rep += 1000;
    }
  }
  cout << rep << endl;
  return 0;
}

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

using ll = long long;
#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

int dp[102][12000];

int main(){
  int N, W;
  cin >> N >> W;
  vector<int> v(N), w(N);
  REP(i, N){
    cin >> v[i] >> w[i];
  }

  REP(i, N){
    REP(j, W+1){
      dp[i+1][j] = max(dp[i][j], dp[i+1][j]);
      dp[i+1][j+w[i]] = max(dp[i+1][j+w[i]], dp[i][j] + v[i]);
    }
  }
  cout << dp[N][W] << endl;
  return 0;
}



Measured memory_bytes: 7800
n=input()
a=int(n[0])
b=int(n[1])
c=int(n[2])
if a>b:
  print(a*111)
elif a<b:
  print((a+1)*111)
else:
  if b>=c:
    print(a*111)
  else:
    print((a+1)*111)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define fast ios::sync_with_stdio(false);cin.tie(NULL)
using namespace std;
#define int long long
#define MOD 1000000007
typedef vector<int> vi;
typedef pair<int,int> pi;
#define inf 1e18
#define For(i,a,b) for (int i = a; i < b; i++)
#define Rep(i,a,b) for (int i = a; i <= b; i++)
#define ps(x,y) fixed << setprecision(y) << x 
#define pb push_back 
#define mp make_pair 

int findXOR(int n) {
    int mod = n % 4;
    if(mod == 0) return n;
    else if(mod == 1) return 1;
    else if(mod == 2) return n+1;
    else if(mod == 3) return 0;
}

int findXOR(int a, int b) {
    return (findXOR(a-1) ^ findXOR(b));
}
 
int32_t main()
{
    fast;
    int a, b; cin >> a >> b;
    cout << findXOR(a, b);

    return 0;
}

Measured memory_bytes: 3580
#include <iostream>
#include <algorithm>
#include <unordered_set>
#include <cstring>
using namespace std;
const int N = 1e6+10;
int a[N];
bool b[N];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    memset(b, true, sizeof (b));
    //unordered_set<int> s;
    
    while (m--) {
        int u, v;
        scanf("%d%d", &u, &v);
       
        if (a[u] >= a[v]) {
            b[v] = false;
        } 
        if (a[u] <= a[v]) {
            b[u] = false;
        } 
        
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) if (b[i]) ans ++;
    
    
    cout << ans << endl;
    return 0;
} 

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

using namespace std;

int main()
{
  int a,b,c;
  cin>>a>>b>>c;
  int minab=min(a,b);
  int count=0;
  for(int i=minab;i>0;i--)
  {
    if(a%i==0 and b%i==0 and count<c)
           count+=1;
    if(a%i==0 and b%i==0 and count==c)
    {
                cout<<i;
                break;
    }   
    else
   		continue;
  return 0;
  }
}

Measured memory_bytes: 256
import qualified Data.Text as T
import qualified Data.Text.IO as T
import qualified Data.Text.Read as T

main :: IO ()
main = do
  (x : a : _) <- map unsafeSignedDecimal . T.words <$> T.getLine :: IO [Int]
  print $ if x < a then 0 else 10

unsafeSignedDecimal :: T.Text -> Int
unsafeSignedDecimal s = case T.signed T.decimal s of
  Right (n, _) -> n


Measured memory_bytes: 508
#include <bits/stdc++.h>
#define REP(i, n) for (int (i) = 0; (i) < (int)(n); i++) 
#define FOR(i, a, b) for(int (i) = a; (i) < (int)b; i++)
#define RREP(i, n) for(int (i)=((int)(n)-1); (i)>=0; i--)
#define RFOR(i, a, b) for(int (i) =((int)(b)-1); (i)>=(int)a; i--)
#define ALL(v) (v).begin(),(v).end()
#define MOD 1000000007
#define NIL -1
#define FI first
#define SE second
#define MP make_pair
#define PB push_back
#define SZ(x)  (int)x.size()
#define SP(x)  setprecision((int)x)


using namespace std ;
typedef long long ll;
using Graph = vector<vector<int>>;
typedef vector<int> vint;
typedef vector<vint> vvint;
typedef vector<string> vstr;
typedef pair<int, int> pii;
const int INF = 1e9;
const ll LINF = 1e18;
const double EPS = 1e-9;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;} //最大公約数
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;} //最小公倍数

//-------------------------------------------------
// 
void yes(){
  cout <<"Yes"<<endl ;
}
void no(){
  cout <<"No"<<endl ;
}


//-------------------------------------------------
// メモ
/*






*/
//-------------------------------------------------


int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  double n, m ;
  cin >> n >> m ;
  double sum = 0 ;
  vector<int> vec(n) ;
  REP(i,n){
    cin >> vec[i] ;
    sum += vec[i] ;
  }
  double a = sum/(4*m) ;
  int cnt = 0 ;
  REP(i,n){
    if(a<=vec[i]){
      cnt++ ;
    }
  }
  
  if(cnt>=m){
    yes() ;
  }
  else{
    no() ;
  }
      
  
  
  
  
  return 0 ;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
def main():
    N,A,B = map(int,input().split())
    ans0 = N//(A+B)
    ans1 = A*ans0
    ans2 = (N-(A+B)*ans0)
    ans1 += min(ans2,A)
    print(ans1)
if __name__ == '__main__':
    main()

Measured memory_bytes: 3060
import Control.Monad

main :: IO ()
main = do
  n <- readLn
  ls <- replicateM n getLine
  mapM_ print $ solve (map (map read . words) ls)

solve :: [[Int]] -> [Int]
solve = map minVal
  where
    minVal :: [Int] -> Int
    minVal [x,y,b,p]
      | b < 5 && p < 2 = min normalVal ((x * 5 + y * 2) `div` 10 * 8)
      | b < 5 && p >= 2 = min normalVal ((x * 5 + y * p) `div` 10 * 8)
      | b >= 5 && p < 2 = min normalVal ((x * b + y * 2) `div` 10 * 8)
      | otherwise = normalVal `div` 10 * 8
      where
        normalVal = x * b + y * p

Measured memory_bytes: 4280
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
int acs(const void *a, const void *b) { 
  return *(int*)a - *(int*)b;
} /* 1,2,3,4.. */
int des(const void *a, const void *b) {
  return *(int*)b - *(int*)a;
} /* 8,7,6,5.. */
int cmp_char(const void *a, const void *b) { 
  return *(char*)a - *(char*)b;
} /* a,b,c,d.. */
int cmp_str(const void *a, const void *b) {
  return strcmp(*(const char **)a, *(const char **)b);
} /* aaa,aab.. */
#define min(a,b) (a < b ? a : b)
#define max(a,b) (a > b ? a : b)
#define rep(i, l, r) for (int i = l; i < r; i++)
#define MAX 100001
#define MOD 1000000007
#define INF 1000000009
typedef long long int lli;

int main(void) {
  lli h, w;
  scanf("%lld %lld", &h, &w);
  if (h == 1 || w == 1) printf("1");
  else printf("%lld\n", (h * w + 1) /2);
  return 0;
}


Measured memory_bytes: 128
from math import factorial

n,m = map(int,input().split())
if abs(n-m)>1:
    print(0)
else:
    if n==m:
        print((factorial(n)**2*2)%(10**9+7))
    else:
        print((factorial(min(n,m))**2*max(n,m))%(10**9+7))


Measured memory_bytes: 4740
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include<iomanip>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <cstdio>

using namespace std;

int main()
{
	int a, b;
	while(cin>>a>>b)
	{
		int c = a+b;
		int ans = 0;
		
		while(c > 0)
		{
			ans++;
			c /= 10;
		}
		cout<<ans<<endl;
	}
	
	return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define FOR(i,k,n)  for(int i = (k);i < (n);++i)
#define REP(i,n)    FOR(i,0,n)
#define ALL(x)      begin(x),end(x)

using namespace std;
using vecint = vector<int>;
using ll = int64_t;

int main()
{
  int n,k;
  cin>>n>>k;
  double p = 0;
  FOR(i,1,n+1) {
    double tmp = 1.0;
    int j = i;
    while (j < k) {
      j *= 2;
      tmp /= 2.0;
    }
    p += tmp / n;
  }
  cout << setprecision(15) << fixed << p << endl;
  return 0;
}


Measured memory_bytes: 256
// inputに入力データ全体が入る
function Main(input) {
    input = input.split("\n");
    var line = input[0].split(" ");
    var num_town = parseInt(line[0]);
    var num_road = parseInt(line[1]);

    var ans = [];


    var first = 0;
    var second = 0;

    for(var i =0; i<num_town;i++){
        ans[i] = 0;
    }

    for(var i =0; i<num_road;i++){
        var temp = input[i+1].split(" ");
//        console.log(temp);
        first = parseInt(temp[0]);
        second = parseInt(temp[1]);
        
        ans[first-1]++;
        ans[second-1]++;
    }

    for(var i =0; i<num_town;i++){
        console.log(ans[i]);
    }
    
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));



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

const static int MAX = 100;
int counter=0;

void bubbleSort(int A[],int N){
  for(int i=0;i<N;i++)
    for(int j=N-1;j>i;j--)
      if(A[j]<A[j-1] && j>0){
	int v=A[j];
	A[j]=A[j-1];
	A[j-1]=v;
	counter++;
      }
}
int main(void){
  int A[MAX],N;

  cin>>N;

  for(int i=0;i<N;i++)cin>>A[i];
  bubbleSort(A,N);

  for(int i=0;i<N;i++){
    if(i>0)
      cout<<" ";
    cout<<A[i];
  }
  cout<<endl<<counter<<endl;

  return 0;

}

Measured memory_bytes: 3088
{-# LANGUAGE BangPatterns #-}

import qualified Data.Vector.Unboxed as V
import Data.Array.IArray (listArray, accumArray, (!))
import Data.Array.MArray
import Data.Array.ST (STUArray, runSTUArray)
import Data.Array.Unboxed (UArray)
import Data.List (sortOn, sortBy, unfoldr, partition)
import Data.Char (isSpace)
import Control.Monad.ST (ST)
import Control.Monad.Trans.State (StateT(..))
import qualified Data.ByteString.Char8 as B

import qualified Data.IntMap as M

import Debug.Trace (trace)

-- utility functions

tr = id
trl l = id

--   Input functions
readInt = B.readInt . B.dropWhile isSpace

readInts :: Int -> B.ByteString -> [Int]
readInts n = take n . unfoldr readInt

readIntsV :: Int -> B.ByteString -> V.Vector Int
readIntsV n = V.unfoldrN n readInt

readIntsA :: Int -> B.ByteString -> UArray Int Int
readIntsA n bs = runSTUArray $ do
  arr <- newArray_ (0,n-1)
  go arr 0 bs
  return arr
  where
    go :: STUArray s Int Int -> Int -> B.ByteString -> ST s ()
    go arr i bs
      | i==n = return ()
      | otherwise = do
        let Just (x,bs') = readInt bs
        writeArray arr i x
        go arr (i+1) bs'

readTsV :: Int -> B.ByteString -> V.Vector (Int,Int)
readTsV n = V.unfoldrN n $ runStateT ((,) <$> StateT readInt <*> StateT readInt)

readTs :: Int -> B.ByteString -> [(Int,Int)]
readTs n = take n . unfoldr readT where
  readT = runStateT ((,) <$> StateT readInt <*> StateT readInt)

readSushis :: Int -> B.ByteString -> [Sushi]
readSushis n = take n . unfoldr readSushi where
  readSushi = runStateT (Sushi <$> StateT readInt <*> StateT readInt)

-- main

data Sushi = Sushi
  { typ :: Int
  , del :: Int
  } deriving (Eq)

instance Show Sushi where 
  show (Sushi t d) = show (t,d)

instance Ord Sushi where
  compare (Sushi t1 d1) (Sushi t2 d2) = compare d1 d2

enumGs fixed canRemove [] base kind = [base + kind*kind]
enumGs fixed [] _ base kind = [base + kind*kind]
enumGs fixed canRemove@(r:rs) (s:ss) base kind
  | M.member (typ s) fixed = enumGs fixed canRemove ss base kind
  | otherwise
    = let !base' = tr $ base - r + (del s)
          kind' = kind + 1 
      in (base + kind*kind) : enumGs (M.insert (typ s) (del s) fixed) rs ss base' kind'

solv k ss = maximum $ enumGs fixed canRemove remain base kind
  where
    !(mostDelicious, remain) = tr $ splitAt k $ sortBy (flip compare) ss
    !(fixed, canRemove) = trl "(fixed, canRemove)" $ part mostDelicious M.empty []
    kind = M.size fixed
    !base = tr $ M.foldl' (+) 0 fixed + sum canRemove
    part [] m s = (m, s)
    part (x:xs) m s
      | M.member (typ x) m = part xs m (del x:s)
      | otherwise = part xs (M.insert (typ x) (del x) m) s

main = do
  [n,k] <- map read . words <$> getLine
  sushi <- sortBy (flip compare) . readSushis n <$> B.getContents
  print $ solv k sushi


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

int main()
{
  int str_size=0;
  char temp[20];
  char str[20];
  cin>>str;

  str_size=strlen(str);
  strcpy(temp, str);
  
  for(int i=0;i<str_size;i++)
    str[i]=temp[str_size-1-i];

  cout<<str<<endl;
  
  return 0;
}



Measured memory_bytes: 3120
def ans():
  N = int(input())
  memo = []
  res = "Yes"
  for _ in range(N):
    W = input()
    if(memo == []):
      memo.append(W)
    elif(W in memo or W[0] != memo[-1][-1]):
      res = "No"
    else:
      memo.append(W)
  print(res)
ans()

Measured memory_bytes: 3060
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

int INF = 1 << 30;

int main() {
    string s;
    cin >> s;
    int N = s.size();

    vector<vector<int>> dp(N + 1, vector<int>(2, INF));
    //dp[i][0] := i ~ N桁を桁下がりがあるないで持つ
    dp[0][0] = 0; //繰り下がりなし

    for(int i = 0; i < N; i++) {
        int n = s[i] - '0';
        dp[i + 1][0] = min(dp[i][0] + n, dp[i][1] + n + 1);
        dp[i + 1][1] = min(dp[i][0] + 10 - n, dp[i][1] + 9 - n);
    }

    cout << min(dp[N][0], dp[N][1] + 1) << endl;
    return 0;
}


Measured memory_bytes: 57988
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define F first
#define S second
#define pb emplace_back
#define pi pair<int,int>
using namespace std;
const int maxn = 1e5 + 4;

int n;
int a[maxn], dp[maxn];

int main(){
	cin>>n;
	for (int i = 0; i < n; ++i){
		cin>>a[i];
	}
	dp[1] = abs(a[0]-a[1]);
	for (int i = 2; i < n; ++i){
		dp[i] = min(dp[i-1] + abs(a[i-1]-a[i]), dp[i-2] + abs(a[i-2]-a[i]));
	}
	cout<<dp[n-1]<<'\n';

}

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

using ll = long long;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

constexpr int I_INF = numeric_limits<int>::max();
constexpr ll L_INF = numeric_limits<ll>::max();

//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

void solve() {
    ll N;
    cin >> N;
    Vl A(N);
    for (ll i = 0; i < N; i++) {
        cin >> A[i];
    }
    sort(A.begin(), A.end(), greater<ll>());
    ll p1 = 0, p2 = 0;
    for (ll i = 0; i < N; i++) {
        if (i & 1)
            p2 += A[i];
        else
            p1 += A[i];
    }
    cout << p1 - p2 << endl;
}

//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

int main() {
#ifdef FASTIO
    cin.tie(0), cout.tie(0);
    ios::sync_with_stdio(false);
#endif
#ifdef FILEINPUT
    ifstream ifs("./in_out/input.txt");
    cin.rdbuf(ifs.rdbuf());
#endif
#ifdef FILEOUTPUT
    ofstream ofs("./in_out/output.txt");
    cout.rdbuf(ofs.rdbuf());
#endif
    solve();
    cout << flush;
    return 0;
}

Measured memory_bytes: 256
import bisect
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
C.sort()

ans = 0
for i in range(N):
  b = B[i]
  a = bisect.bisect_left(A, b)
  c = N - bisect.bisect_right(C, b)
  ans += a*c
  
print(ans)

Measured memory_bytes: 23360
#include <iostream>
#include<vector>
using namespace std;
vector<int>  memo;
int f(int n){
    if(n<0)
        return 0;
    if(n==0)
        return 1;
    if ( memo[n]!= -1 )
        return memo[n];
    return f(n-1)+f(n-2)+f(n-3);
}
 
int main(){
    int n;
    memo.resize(31,-1);
    while(1){
        cin >> n;
        if(n==0)
            break;
        int num=f(n);
        cout <<num/10/365+1<< endl;
    }
    return 0;  
}  

Measured memory_bytes: 1196
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9+7;

int main()
{
	ll n,k;
	cin >> n >> k;
	vector<ll> a(n);
	for(int i = 0;i<n;i++)cin >> a[i];

	vector<ll> asum(n+1),bsum(n+1);

	for(int i = 0;i<n;i++)
	{
		asum[i+1] = asum[i] + a[i];
		bsum[i+1] = bsum[i] + max(0LL,a[i]);
	}

	ll ans = 0;

	for(int i = 0;i<n-k+1;i++)
	{
		ll now = 0;

		ll A= bsum[i] - bsum[0];
		ll B = max(0LL, asum[i+k] - asum[i]);
		ll C = bsum[n] - bsum[i+k];
	//cout << A << ' ' << B <<' '<< C << endl;
		ans = max(A+B+C,ans);
	}
	cout << ans << endl;

}


Measured memory_bytes: 5600
#include <iostream>
using namespace std;
int main() {
  int n;
  double m;
  cin >> n >> m;
  int a[n];
  int c = 0;
  double s = 0.0;
  for(int i = 0; i < n; i++) {
    cin >> a[i];
    s += a[i];
  }
  for(int i = 0; i < n; i++) {
    if(a[i] >= s/(4.0*m)) c++;
  }
  if(c >= m) cout << "Yes";
  else cout << "No";
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<stack>
#include<cstring>
#include<utility>
#include<cmath>
#include<assert.h>
#include<set>

#define int long long
using namespace std;
#define rep(i, n) for(int i=0;i<(n);++i)
typedef pair<int, int> pii;
const int INF = 1l << 60;
#define u_b upper_bound
#define l_b lower_bound

int K;
int A[100100];

int f(int n) {
    rep(i, K) {
        n = n / A[i] * A[i];
    }
    return n;
}

signed main() {
    cin >> K;
    rep(i, K) {
        cin >> A[i];
    }
    int mini;
    {
        int cant = -1;//2人未満 if n in [0,cant]
        int can = INF;//2人以上 if n in [can,]
        while (can - cant > 1) {
            int m = (cant + can) / 2;
            if (f(m) < 2)cant = m;
            else can = m;
        }
        mini = cant + 1;
        if (f(mini) != 2) {
            cout << -1 << endl;
            return 0;
        }
    }

    int maxi;
    {
        int can = -1;//2人以下 if n in [0,can]
        int cant = INF;//2人より多い if n in [cant,]
        while (cant - can > 1) {
            int m = (can + cant) / 2;
            if (f(m) <= 2)can = m;
            else cant = m;
        }
        maxi = cant - 1;
    }
    cout << mini << " " << maxi << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main(void){
  int a,b;
  cin >> a >> b;
  if ((a + b) % 2 == 0)
    cout << abs(a + b) / 2 << endl;
  else
    cout << "IMPOSSIBLE" << endl;

  return 0;
}


Measured memory_bytes: 256
#include<iostream>

using namespace std;

int n, M[100][100], W = 0, G = 1, B = 2;

void dijkstra () {

    int minv, d[100], color[100], i, u, v;

    for (i = 0; i < n; i++) {
        d[i] = (1 << 21);
        color[i] = W;
    }

    d[0] = 0;
    color[0] = G;

    while (1) {

        minv = (1 << 21);
        u = -1;

        for (i = 0; i < n; i++) {
            if (minv > d[i] && color[i] != B) {
                u = i;
                minv = d[i];
            }
        }

        if (u == -1) {
            break;
        }

        color[u] = B;

        for (v = 0; v < n; v++) {
            if (color[v] != B && M[u][v] != (1 << 21)) {
                if (d[v] > d[u] + M[u][v]) {
                    d[v] = d[u] + M[u][v];
                    color[v] = G;
                }
            }
        }

    }

    for (i = 0; i < n; i++) {
        cout << i << " " << (d[i] == (1 << 21) ? -1 : d[i]) << endl;
    }

}

int main () {

    int k, c, u, v, i, j;

    cin >> n;
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            M[i][j] = (1 << 21);
        }
    }

    for (i = 0; i < n; i++) {
        cin >> u >> k;
        for (j = 0; j < k; j++) {
             cin >> v >> c;
             M[u][v] = c;
        }
    }

    dijkstra ();

    return 0;

}

Measured memory_bytes: 3088
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1e5+5;
const int INF = 1e9;
int x[maxn];

int main()
{
    int n,k;
    int i;

    scanf("%d%d",&n,&k);
    int pos = -1;
    for(i = 0;i < n;i++)
    {
        scanf("%d",&x[i]);
        if(x[i] >= 0 && pos == -1) pos = i;
    }
    if(pos == -1) printf("%d\n",-x[n-k]);
    else if(pos == 0) printf("%d\n",x[k-1]);
    else
    {
        int l = pos-1,r = pos;
        int sum = INF;
        if(n-pos >= k) sum = x[r+k-1];
        int temp1,temp2;
        for(;l >= 0;l--)
        {
            if(n-l >= k)
            {
                temp1 = 2*(-x[l])+x[l+k-1];
                temp2 = (-x[l])+2*x[l+k-1];
                sum = min(temp1,min(temp2,sum));
            }
        }
        printf("%d\n",sum);
    }


    return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
long long INF = 1e18;

int main(){
    string s;
    cin>>s;
    long long ans = 0;

    for(int mask=0 ;mask < (1 << s.size()-1); mask++){
        long long result = 0;
        long long add = s[0] - '0';
        for(int i=0 ; i<s.size()-1; i++ ){
            if(mask & (1 << i)){
                result += add;
                add =0;
            }
            add = add * 10 + s[i+1] - '0';
        }
        result +=add;
        ans += result;
    }
    
    

    cout<< ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define INF (int)(1123456789)
#define LINF (long long int)(112345678901234567)
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define PB push_back
#define SP << " " <<

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;

__attribute__((constructor))
void initial(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed <<setprecision(15);
}


int main(void){
	ll X;
    cin >> X;
    ll ans = 0;
    
    while(X>=500){
        X -= 500;
        ans += 1000;
    }

    while(X>=5){
        X -= 5;
        ans += 5;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
function Main(input){
  var X = Number(input);
  var f = 0;
  for(var i of input){
    f += Number(i);
  }
  if(X%f==0){
    console.log('Yes');
  }else{
    console.log('No');
  }
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

using namespace std;

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, b, e) for (int i = (b); i <= (int)(e); i++)

const int N_MAX = 2500;
const int M_MAX = 5000;
const int C_I_MAX = 100000;
const int P_MAX = 100000;

int N, M, P;
int A[M_MAX];
int B[M_MAX];
int C[M_MAX];
vector<int> to[N_MAX + 5];
vector<int> ot[N_MAX + 5];
bool reachable_from_1[N_MAX + 5];
bool reachable_to_N[N_MAX + 5];
vector<tuple<int, int, int>> edges;
bool ok[N_MAX + 5];
const int INF = 1001001001;
/* 1. 1から到達しない点のメモ */
/* 2. nから到達しない点のメモ */
/* 3. ベルマンフォードで最短を見つける */

void dfs(int v)
{
  if (reachable_from_1[v])
    return;
  reachable_from_1[v] = true;
  for (int u : to[v])
  {
    dfs(u);
  }
}

void rdfs(int v)
{
  if (reachable_to_N[v])
    return;
  reachable_to_N[v] = true;
  for (int u : ot[v])
  {
    rdfs(u);
  }
}

int solve()
{
  scanf("%d%d%d", &N, &M, &P);
  REP(i, M)
  {
    int a, b, c;
    cin >> a >> b >> c;
    --a;
    --b;
    c -= P;
    c = -c;
    edges.emplace_back(a, b, c);
    to[a].push_back(b);
    ot[b].push_back(a);
  };
  dfs(0);
  rdfs(N - 1);
  REP(i, N) ok[i] = reachable_from_1[i] & reachable_to_N[i];
  { // bellman-ford
    vector<int> d(N, INF);
    d[0] = 0;
    bool upd = true;
    int step = 0;
    while (upd)
    {
      upd = false;
      REP(i, M)
      {
        int a, b, c;
        tie(a, b, c) = edges[i];
        if (!ok[a])
          continue;
        if (!ok[b])
          continue;
        int newD = d[a] + c;
        if (newD < d[b])
        {
          upd = true;
          d[b] = newD;
        }
      }
      step++;
      if (step > N) {
        puts("-1");
        return 0;
      }
    }
    int ans = -d[N-1];
    ans = max(ans, 0);
    cout << ans << endl;
  }
}

int main()
{
  solve();
  return 0;
}


Measured memory_bytes: 640
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using uint = unsigned int;
using ll = long long;
enum : int { M = (int)1e9 + 7 };
enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
#include"rprint2.hpp"
#include"debug_deque.hpp"
#define vector DebugDeque
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(prints) FUNC(printe) FUNC(printw) FUNC(printew) FUNC(printb) FUNC(printd) FUNC(printde);
#endif

#include<unistd.h>
struct Buffer{
    int idx;
    enum { chunk = 1 << 16 };
    char buf[chunk];
    Buffer(){ init(); }
    void init(){ idx = 0; read(0, buf, chunk); }
    void check(){ if(idx == chunk){ init(); } }
    int next(){
        static char notDigits[256] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1, 0,0,0,0,0,0,0,0,0,0,};
        int ret = 0, sign = 1;
        while(check(), notDigits[(int)buf[idx]]){ idx++; }
        if(check(), buf[idx] == '-'){ sign = -1; idx++; }
        while(check(), !notDigits[(int)buf[idx]]){ ret = ret * 10 + buf[idx++] - '0'; }
        return sign * ret;
    }
};

void out(int num){
    if(!num){
        putchar('0');
        return;
    }
    char buf[16];
    int idx = 0;
    while(num){
        // auto ret = div(num, 10);
        // buf[idx] = ret.rem + '0';
        // num = ret.quot;
        // idx++;
        buf[idx] = num % 10 + '0';
        num = num / 10;
        idx++;
    }
    for(int i = idx - 1; i >= 0; i--){
        putchar(buf[i]);
    }
}

int main(){
    // cin.tie(0);
    // ios::sync_with_stdio(false);
    Buffer buf;
    const int lim = 1e5;
    vector<char> prime(lim + 1, true);
    prime[0] = prime[1] = false;
    for(int i = 2; i <= lim; i++){
        if(prime[i]){
            for(int j = i + i; j <= lim; j += i){
                prime[j] = false;
            }
        }
    }
    vector<int> accs(lim + 1);
    for(int i = 1; i <= lim; i++){
        accs[i] = accs[i - 1] + (i & 1 && prime[i] && prime[(i + 1) / 2]);
    }
    // int q; cin >> q;
    int q = buf.next();
    // stringstream ss;
    for(int i = 0; i < q; i++){
        // int l, r;
        // cin >> l >> r;
        int l = buf.next(), r = buf.next();
        // cout << accs[r] - accs[l - 1] << '\n';
        // ss << accs[r] - accs[l - 1] << '\n';
        out(accs[r] - accs[l - 1]);
        putchar('\n');
    }
    // cout << ss.str();
}


Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define REPR(i,n) for (int i=(int)(n)-1;i>=0;--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define valid(y,x,h,w) (0<=y&&y<h&&0<=x&&x<w)
#define tpl(...) make_tuple(__VA_ARGS__)
const int INF = 0x3f3f3f3f;
const double EPS = 1e-8;
const double PI = acos(-1);
const int dy[] = {-1,0,1,0};
const int dx[] = {0,1,0,-1};
typedef long long ll;
typedef pair<int,int> pii;
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 Ch,typename Tr,typename C,typename=decltype(begin(C()))>basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>&os,
const C& c){os<<'[';for(auto i=begin(c);i!=end(c);++i)os<<(i==begin(c)?"":" ")<<*i;return os<<']';}
template<class S,class T>ostream&operator<<(ostream &o,const pair<S,T>&t){return o<<'('<<t.first<<','<<t.second<<')';}
template<int N,class Tp>void output(ostream&,const Tp&){}
template<int N,class Tp,class,class ...Ts>void output(ostream &o,const Tp&t){if(N)o<<',';o<<get<N>(t);output<N+1,Tp,Ts...>(o,t);}
template<class ...Ts>ostream&operator<<(ostream&o,const tuple<Ts...>&t){o<<'(';output<0,tuple<Ts...>,Ts...>(o,t);return o<<')';}
template<class T>void output(T t,char z=10){if(t<0)t=-t,putchar(45);int c[20];
int k=0;while(t)c[k++]=t%10,t/=10;for(k||(c[k++]=0);k;)putchar(c[--k]^48);putchar(z);}
template<class T>void outputs(T t){output(t);}
template<class S,class ...T>void outputs(S a,T...t){output(a,32);outputs(t...);}
template<class T>void output(T *a,int n){REP(i,n)cout<<a[i]<<(i!=n-1?',':'\n');}
template<class T>void output(T *a,int n,int m){REP(i,n)output(a[i],m);}
template<class T>bool input(T &t){int n=1,c;for(t=0;!isdigit(c=getchar())&&~c&&c-45;);
if(!~c)return 0;for(c-45&&(n=0,t=c^48);isdigit(c=getchar());)t=10*t+c-48;t=n?-t:t;return 1;}
template<class S,class ...T>bool input(S&a,T&...t){input(a);return input(t...);}
template<class T>bool inputs(T *a, int n) { REP(i,n) if(!input(a[i])) return 0; return 1;}

vector<pii> g[100001];
int color[100001];

void func(int v, int c) {
  color[v] = c;
  FOR(it, g[v]) {
    if (color[it->first] != -1) continue;
    if (it->second % 2 == 0) {
      func(it->first, c);
    }
    else
    {
      func(it->first, !c);
    }
  }
}

int main() {
  int n;
  while (cin >> n) {
    REP(i, n) g[i].clear();
    REP(i, n - 1) {
      int u, v, w;
      input(u, v, w);
      // outputs(u,v,w);
      u--;
      v--;
      g[u].push_back(pii(v, w));
      g[v].push_back(pii(u, w));
    }
    memset(color, -1, sizeof(color));
    func(0, 0);
    REP(i, n) {
      output(color[i]);
    }
  }
}


Measured memory_bytes: 7552
#include<iostream>
using namespace std;
int sum[2001];
int main()
{
	for(int i = 0; i < 1001; ++i)
	{
		for(int j = 0; j < 1001; ++j)
		{
			sum[i+j]++;
		}
	}
	int n;
	while(cin>>n) 
	{
		long long ans=0;
		for(int i = 0; i <= 1000; ++i)
		{
			for(int j = 0; j <= 1000; ++j)
			{
				if(n-i-j>2001) continue;
				if(n-i-j<0) break;
				ans+=sum[n-i-j];
			}
		}
		cout<<ans<<endl;
	}
  return 0;
}

Measured memory_bytes: 1164
// ABC157E - Simple String Queries

#include <bits/stdc++.h>
using namespace std;

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

	vector< set<int> > alpha(26);

	for (int i = 0; i < N; i++) {
		char c;
		cin >> c;
		alpha.at(c - 'a').insert(i + 1);
	}

	int Q;
	cin >> Q;
	for (int i = 0; i < Q; i++) {
		int op;
		cin >> op;
		if (op == 1) {
			int iq;
			char cq;
			cin >> iq >> cq;

			for (int j = 0; j < 26; j++) {
				alpha.at(j).erase(iq);
			}
			alpha.at(cq - 'a').insert(iq);
		} else if (op == 2) {
			int l, r;
			cin >> l >> r;

			int answer = 0;
			for (int j = 0; j < 26; j++) {
				set<int>::iterator it;
				it = alpha.at(j).lower_bound(l);
				if ((it != alpha.at(j).end())&&(*it <= r)) {
					answer++;
				};
			}
			cout << answer << endl;
		}
	}
}


Measured memory_bytes: 23680
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int qp(int a,int n)
{
	if (n == 0) return 1;
	int ans = qp(a,n / 2);
	ans *= ans;
	if (n & 1) ans *= a;
	return ans;
}

int main()
{
	int n,k;
	scanf("%d%d",&n,&k);
	int ans = 1;
	ans *= qp(k-1,n-1);
	ans *= k;
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
/*#include <string>*/
#include <iostream>
#include <vector>

using namespace std;



int main(void){

    string S[3];
    cin >> S[0] >> S[1] >> S[2];

    char pt[3] = {0, 0, 0};
    char player[3] = {'A', 'B', 'C'};

    int now = 0;
    while (true){
        if(S[now].size() == pt[now]){
            cout << player[now] << endl;
            break;
        }
        char target = S[now][pt[now]];
        pt[now]++;

        if(target == 'a'){
            now = 0;
        }
        else if(target == 'b'){
            now = 1;
        }
        else if(target == 'c'){
            now = 2;
        }
    }
    
}



Measured memory_bytes: 256