akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

template <typename T>
struct Edge { int src, dst; T cost;
    Edge(int dst, T cost) : src(-1), dst(dst), cost(cost) { }
    Edge(int src, int dst, T cost) : src(src), dst(dst), cost(cost) { }
};
template <typename T> using Edges = vector<Edge<T>>;
template <typename T> using WeightedGraph = vector<Edges<T>>;
template <typename T> using Matrix = vector<vector<T>>;

template <typename T>
vector<T> dijkstra(const WeightedGraph<T> &g, int s) {
    const T INF = numeric_limits<T>::max();
    vector<T> dist(g.size(), INF);
    vector<int> prev(g.size(), -1);
    using Pi = pair<T, int>;
    priority_queue<Pi, vector<Pi>, greater<Pi>> que;
    dist[s] = 0; que.emplace(dist[s], s);
    while (!que.empty()) {
        T cost; int u; tie(cost, u) = que.top(); que.pop();
        if (dist[u] < cost) continue;
        for (auto &e: g[u]) {
            int v = e.dst; T nc = e.cost;
            if (dist[v] <= dist[u] + nc) continue;
            dist[v] = dist[u] + nc; prev[v] = u;
            que.emplace(dist[v], v);
        }
    }
    return dist;
}

int main() {
    int n; cin >> n;
    WeightedGraph<long long> g(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v, w; cin >> u >> v >> w; u--, v--;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    auto d = dijkstra(g, 0);
    for (int i = 0; i < n; i++) {
        cout << d[i] % 2 << endl;
    }
    return 0;
}

Measured memory_bytes: 8832
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <functional>
#include <utility>
#include <fstream>

using namespace std;

#define ll long long
#define INF 2000000000
#define LINF 2000000000000000000
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define dum(x) cout<<#x<<'='<<x<<endl
#define dum2(x,y) cout<<#x<<'='<<x<<' '<<#y<<'='<<y<<'\n'<<endl
#define dum3(x,y,z) cout<<#x<<'='<<x<<' '<<#y<<'='<<y<<' '<<#z<<'='<<z<<'\n'<<endl
#define darr(arr,n) rep(i,(n-arr)){cout<<*(arr+i)<<' ';}cout<<endl

//ifstream in("Text.txt");cin.rdbuf(in.rdbuf());

int main() {
    int N, M;
    cin >> N;
    map<string, int>mp;
    rep(i, N) {
        string S;
        cin >> S;
        mp[S]++;
    }
    cin >> M;
    rep(i, M) {
        string S;
        cin >> S;
        mp[S]--;
    }
    int ma = 0;
    for (auto itr = mp.begin(); itr != mp.end(); ++itr) {
        ma = max(ma, itr->second);
    }
    cout << ma << endl;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define per(i,a,b) for(int i=b-1;i>=(a);i--) 
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define lb(x) (x&-(x))
const int N = 101010;
int a[200];
int main(){
	int maxx=INT_MIN;
	int maxxi,minni;
	int minn=INT_MAX;
	int n;
	cin>>n;
	rep(i,0,n) 
	{
		scanf("%d",&a[i]);
		if(a[i]>maxx)
		{
			maxx=a[i];
			maxxi=i;
		}
		if(a[i]<minn)
		{
			minn=min(minn,a[i]);
			minni=i;
		}
	}
	
	
	printf("%d\n",n+n-1);
	if(maxx+minn>=0)
	{	 
		 rep(i,0,n)
		 {
		 	printf("%d %d\n",maxxi+1,i+1);
		 	a[i]+=maxx;
		 }
		 
//		 rep(i,0,n) cout<<a[i]<<" ";cout<<endl;
		rep(i,0,n-1)
		{
			printf("%d %d\n",i+1,i+2);
			a[i+1]+=a[i];
		}
	}
	else
	{
		 rep(i,0,n)
		 {
		 	printf("%d %d\n",minni+1,i+1);
		 	a[i]+=minn;
		 }		
//		 rep(i,0,n) cout<<a[i]<<" ";cout<<endl;		
		per(i,0,n-1)
		{
			printf("%d %d\n",i+2,i+1);
			a[i]+=a[i+1];
		}
	}
	
	

    return 0;
}


Measured memory_bytes: 256
N = int(input())
A,B = map(int,input().split())
P = list(map(int,input().split()))
First = 0
Second = 0
Third = 0
for i in P:
  if i <= A:
    First += 1
  elif i <= B:
    Second += 1
  else:
    Third += 1
Answer = min(First,Second,Third)
print(Answer)

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

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<int> > act(n, vector<int>(3));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 3; j++) cin >> act[i][j];
    }

    vector<vector<int> > dp(n, vector<int>(3));
    for (int i = 0; i < 3; i++) dp[0][i] = act[0][i];
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                if (k != j) dp[i][j] = max(dp[i][j], dp[i - 1][k] + act[i][j]);
            }
        }
    }

    cout << max({dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]}) << '\n';
}

Measured memory_bytes: 11136
#include<iostream>
#include<math.h>
using namespace std;

int main(){
    int n,y;
    cin>>n>>y;

    int m1=-1;
    int m2=-1;
    int m3=-1;
    
    for(int i=0;i<=n;i++){
        for(int j=0;i+j<=n;j++){
            if(y==10000*i+5000*j+1000*(n-i-j)){
                m1=i;
                m2=j;
                m3=n-i-j;
            }
        }
    }
    cout<<m1<<" "<<m2<<" "<<m3<<endl;

    return 0;
}

Measured memory_bytes: 256
n = int(input())

s = {}

for i in range(n):
    si = input()
    if si in s.keys():
        s[si] += 1
    else:
        s[si] = 1

sorted_s = sorted(s.items(), key=lambda x:x[1], reverse=True)
max_v = sorted_s[0][1]
ans = []
for i in range(len(sorted_s)):
    if max_v == sorted_s[i][1]:
        ans.append(sorted_s[i][0])
    else:
        break
ans.sort()
for a in ans:
    print(a)

Measured memory_bytes: 45788
###==================================================
### import
#import bisect
#from collections import Counter, deque, defaultdict
#from copy import deepcopy
#from functools import reduce, lru_cache
#from heapq import heappush, heappop
#import itertools
#import math
#import string
import sys
### stdin
def input(): return sys.stdin.readline()
def iIn(): return int(input())
def iInM(): return map(int, input().split())
def iInM1(): return map(int1, input().split())
def iInLH(): return list(map(int, input().split()))
def iInLH1(): return list(map(int1, input().split()))
def iInLV(n): return [iIn() for _ in range(n)]
def iInLV1(n): return [iIn()-1 for _ in range(n)]
def iInLD(n): return [iInLH() for _ in range(n)]
def iInLD1(n): return [iInLH1() for _ in range(n)]
def sInLH(): return list(input().split())
def sInLV(n): return [input().rstrip("\n") for _ in range(n)]
def sInLD(n): return [sInLH() for _ in range(n)]
### stdout
def OutH(lst): print(*lst)
def OutV(lst): print(*lst, sep="\n")
### setting
sys.setrecursionlimit(10 ** 6)
### utils
int1 = lambda x: int(x) - 1
### constants
INF = int(1e9)
MOD = 1000000007
dx = (-1, 0, 1, 0)
dy = (0, -1, 0, 1)
###---------------------------------------------------

N = iIn()

ans = 0
for k in range(1, N+1):
    ans += k * (N // k) * (N // k + 1) // 2

print(ans)

Measured memory_bytes: 63708
N, X = map(int, input().split())
A = [X] + list(map(int, input().split()))

def gcd(n, m):
    if m == 0:
        return n
    return gcd(m, n % m)

B = [abs(a - A[0]) for a in A]
ans = 0
for d in B:
    ans = gcd(ans, d)
print(ans)


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

using namespace std;

typedef long long ll;
const ll INF = 1LL<<60;

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

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; }

ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}



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

  ll N, K;
  cin >> N >> K;

  ll ans = 0;
  for(ll d = 1; K + d <= N; d++){
    ans += N / (K+d) * d + max(0LL, N % (K+d)-K+1);
  }

  if(K == 0){
    cout << N * N << endl;
  }else{
    cout << ans << endl;
  }
  
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<cstring>
#include<sstream>
#include<algorithm>
#include<iomanip>

using std::cout;
using std::endl;
using std::flush;
using std::cin;

namespace Util{
    using StringVector = std::vector<std::string>;

    /*
       @ 目的: 文字列分割
    */
    StringVector split( const std::string &s, const std::string &delim = std::string(" ") ){
       const int len = s.size();
       char tmp[len+1];
       strcpy( tmp, s.c_str() );

       std::vector<std::string> res;

       char *tmpStr = std::strtok( tmp, delim.c_str() );
       if( tmpStr == NULL ) return res;

       while( tmpStr != NULL ){
           //cout << tmpStr << endl;
           res.push_back( tmpStr );
           tmpStr = NULL;
           tmpStr = std::strtok( NULL, " " );
       }
    return res;
    }

    /*
       @ 目的: 数字等を文字列に固める
    */
    template<typename T>
    std::string toString( T data, int width = 0 ){
       std::stringstream ss;
       ss << std::setw(width) << data;
    return ss.str();
    }
    template<> std::string toString( bool flg, int width ){
       if( width == 1 && flg ) return std::string("T");
       if( width == 1 && !flg ) return std::string("F");
       if( flg ) return std::string("true");
    return std::string("false");
    }
}


namespace Original{
    using Data  = std::vector<int>;
    using Table = std::vector< Data >;
}

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

    // めちゃくちゃな値をセットしておく
    const int INF = 123456789;

    // n, m, x をそれぞれ取得
    std::string tmpNum;
    std::getline( cin, tmpNum );
    Util::StringVector t = Util::split( tmpNum );
    int n = std::atoi( t[0].c_str() );
    int m = std::atoi( t[1].c_str() );
    int x = std::atoi( t[2].c_str() );

    // テーブルとして取得( 二次元配列風 )
    Original::Table table;
    for( int i = 0; i < n; i++ ){
         std::string s;
         getline( cin, s );
         Util::StringVector sv = Util::split( s );
         Original::Data d;
         for( int j = 0; j < m+1; j++ ){
              d.push_back( std::atoi( sv[j].c_str() ) );
         }
         table.push_back( d );
    }

    // 初期値は INFとする
    int ans = INF;

    // bit全探索
    for( int bit = 0; bit < (1 << n); bit++ ){
         std::vector<int> vec(m+1,0);
         for( int i = 0; i < n; i++ ){
              if( (bit >> i) & 1 ){
                  vec[0] += table[i][0];
                  for( int j = 1; j <= m; j++ ) vec[j] += table[i][j];
              }
         }

         bool isAllowed = true;
         for( int i = 1; i <= m; i++ ){
              // todo: もしエラーなら "<=" とかにしてみる
              if( vec[i] < x ){ isAllowed = false; break; }
         }

         if( isAllowed ) ans = std::min( ans, vec[0] );
    }

    if( ans == INF ) cout << -1 << endl;
    else             cout << ans << endl;
return 0;
}

Measured memory_bytes: 3652
N,M=map(int,input().split())
S=list(map(int,input().split()))
S.sort()

TRADE=[[0 for j in range(2)] for i in range(M)]

for i in range(M):
    B,C=map(int,input().split())
    TRADE[i][0]=B
    TRADE[i][1]=C


T=sorted(TRADE,key=lambda x:x[1],reverse=True)


TLEN=0
pos=0
flag=True
while TLEN<M and flag==True:
    for i in range(T[TLEN][0]):
        if S[pos]<T[TLEN][1]:
            S[pos]=T[TLEN][1]
            pos+=1
        else:
            flag=False
            break
        if pos>len(S)-1:
            flag=False
            break
    TLEN+=1

print(sum(S))

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


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

typedef pair<int,int> P;
#define ll long long
#define ld long double
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
#define sz(x) ((int)(x).size())
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
#define all(x) (x).begin(),(x).end()

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

int main()
{
    ll n;cin >> n;
    //vector<bool> isprime(n, true);
    vector<ll> counter(n+1, 0);
    ll ans = 0;
    //isprime[0] = false;
    //isprime[1] = false;
    for (ll i = 1; i <= n ; i++)
    {
        for (ll j = 1; i*j <=n; j++)
        {
            //if(i!=1)isprime[i*j]=false;
            counter[i*j]++;
        }
        
    }
    
    for (ll i = 1; i <=n; i++)
    {
        ans += i*(counter[i]);
    }
    cout << ans << endl;
    // cout << counter[n] << endl;
    
    

}

Measured memory_bytes: 81384
var
    i,j,k,ans,n:longint;
    s:array[0..110] of longint;
    f:array[0..110,0..110,0..110] of boolean;
procedure prime(x:longint);
begin
    j:=2;
    while x>=j do
    begin
        while x mod j=0 do
        begin
            inc(s[j]);
            x:=x div j;
        end;
        inc(j);
    end;
end;
begin
    read(n);
    fillchar(s,sizeof(s),0);
    for i:=2 to n do prime(i);
    fillchar(f,sizeof(f),true);
    ans:=0;
    for i:=2 to n do
        for j:=2 to n do
            if i<>j then
            begin
                if (s[i]>=2) and (s[j]>=24) then inc(ans);
                if (s[i]>=4) and (s[j]>=14) then inc(ans);
                if (s[i]>=2) and (s[j]>=4) then 
                    for k:=2 to n do
                        if (i<>k) and (j<>k) then
                            if s[k]>=4 then 
                                if f[i,j,k] then
                                begin 
                                    inc(ans);
                                    f[i,j,k]:=false;
                                    f[i,k,j]:=false;
                                end;
            end;
    for i:=1 to n do
        if s[i]>=74 then inc(ans);
    writeln(ans);
end.

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

bool vis[55][55];
char G[55][55];
int path[55][55];
int h,w;
int dx [ 4 ] = { 0 , 1 , 0 , -1 };
int dy [ 4 ] = { -1 , 0 , 1 , 0 };

int bfs()
{
	queue <pair < int , int >> q;
    q.push ({ 0 , 0 });
    vis [ 0 ] [ 0 ] = 1 ;
     while (! q.empty ()) {
        auto u = q.front ();
        q.pop ();
        int x = u.first, y=u.second;
        
 
        if (x == w- 1  and y == h- 1 ) return path [y] [x];
 
        for(int i=0;i<4;i++) {
             int xx = x + dx [i];
             int yy = y + dy [i];
             if ( 0 <= xx and xx <w &&  0 <= yy and yy <h) {
                 if (G [yy] [xx] == '.'  && vis [yy] [xx] == 0 ) {
                    vis [yy] [xx] = 1 ;
                    path [yy] [xx] = path [y] [x] + 1 ;
                    q.push ({xx, yy});
                }
            }
        }
    }
 
    return  0 ;
}

int main() {
	 cin >> h >> w;
	 for(int i=0;i<h;i++)
	 {
	 	for (int j=0;j<w;j++)
	 	{
	 		cin>>G[i][j];
	 	}
	 }
   
 
    int ans =0, res = bfs ();
     if (! res) ans = -1 ;
     else {
        ans = h * w -res- 1 ;
	    for(int i=0;i<h;i++)
		 {
		 	for (int j=0;j<w;j++)
		 	{
		 	      if (G [i] [j] == '#' )
		 	          ans--;
		 	}
		 }
       
    }
 
    cout<<ans;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long

const int N = 1e5 + 5;


int32_t main()
{
	IOS;
	int m1, d1, m2, d2;
	cin >> m1 >> d1 >> m2 >> d2;
	if(m2 == m1 + 1 && d2 == 1)
		cout << 1;
	else
		cout << 0;
	return 0;	
}

Measured memory_bytes: 256
N = int(input())
h = list(map(int, input().split()))
dp = [float('inf')]*N
dp[0] = 0
for i in range(N-2):
    dp[i+1] = min(dp[i+1],dp[i]+abs(h[i]-h[i+1]))
    dp[i+2] = min(dp[i+2],dp[i]+abs(h[i]-h[i+2]))
print(min(dp[N-1],dp[N-2]+abs(h[N-2]-h[N-1])))

Measured memory_bytes: 13928
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <iomanip>
#include <math.h>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <functional>

using namespace std;

typedef long long int ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, int> pli;
typedef std::pair<ll, ll> pll;

#define FOR(i,n,m) for(ll i=(ll)(m);i<(ll)(n);++i)
#define REP(i,n) FOR(i,n,0)
#define IREP(i,n) for(ll i=(ll)(n);i>=0;--i)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

ll m[100005];

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

int main()
{
	int N, X;
	cin >> N >> X;
	REP(i, N)
	{
		int x;
		cin >> x;
		m[i] = abs(x - X);
	}

	ll ans = m[0];
	REP(i, N)
	{
		ans = gcd(ans, m[i]);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
const int mx = 100005;
int n, c[mx], a, b, j = 1, ans[mx], sm;
bool used[mx];
vector<int> v[mx];
stack<int> st;

int main(){
    scanf("%d", &n);
    rep(i,n-1){
        scanf("%d%d", &a, &b);
        a--; b--;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    rep(i,n) scanf("%d", c+i);
    sort(c, c+n, greater<int>());
    rep(i,n-1) sm += c[i+1];
    st.push(0);
    ans[0] = c[0]; used[0] = true;
    while(!st.empty()){
        int t = st.top(); st.pop();
        for(int it : v[t]){
            if(used[it]) continue;
            ans[it] = c[j++];
            used[it] = true;
            st.push(it);
        }
    }
    printf("%d\n", sm);
    rep(i,n) printf("%d%s", ans[i], i != n-1 ? " " : "\n");
}

Measured memory_bytes: 3072
#include <iostream>
#include <string>

using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    for (int i=0; i<n; i++) {
        if (s[i] == '1') s[i] = '9';
        else if (s[i] == '9') s[i] = '1';
    }

    cout << s << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main{
 public static void main(String args[]){
  boolean flag=false;
  Scanner scan=new Scanner(System.in);
  String s;

  s=scan.next();
  long a=Long.parseLong(s);
  s=scan.next();
  long b=Long.parseLong(s);
  s=scan.next();
  long c=Long.parseLong(s);
  s=scan.next();
  long k=Long.parseLong(s);
 
  long ans;
  if(k%2==0)ans=a-b;
  else ans=b-a;


  System.out.println(ans);
 }
}
/*
(now,before)(high,middle,low)
1回の操作では、sumが2*sumになる
nh=sum-bh
nb=sum-bm;
nh-nb=-nh+bm<-これの繰り返し(sumに影響しない)
求める値は1回の操作でbh-bm->bm-bhになるだけ
*/


Measured memory_bytes: 35408
from collections import deque
import sys
input = sys.stdin.readline

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(lambda x : int(x) - 1, input().split())
c = [input().rstrip() for _ in range(H)]
INF = 10**18
dist = [[[(INF, INF)] * 4 for _ in range(W)] for _ in range(H)]
dist[x1][y1] = [(1, 0)] * 4
dq = deque()
for i in range(4):
    dq.append((dist[x1][y1][i], x1, y1, i))
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
while dq:
    d, x, y, i = dq.popleft()

    if d > dist[x][y][i]:
        continue

    for j in range(4):
        nd = (d[0] + 1, 0)
        if dist[x][y][j] > nd:
            dist[x][y][j] = nd
            dq.append((nd, x, y, j))

    nx = x + dx[i]
    ny = y + dy[i]
    if nx < 0 or H <= nx or ny < 0 or W <= ny or c[nx][ny] == '@':
        continue
    if d[1] < K:
        nd = (d[0], d[1] + 1)
        if dist[nx][ny][i] > nd:
            dist[nx][ny][i] = nd
            dq.appendleft((nd, nx, ny, i))
    else:
        nd = (d[0] + 1, 1)
        if dist[nx][ny][i] > nd:
            dist[nx][ny][i] = nd
            dq.append((nd, nx, ny, i))
ans = min(dist[x2][y2])[0]
print(ans if ans < INF else -1)


Measured memory_bytes: 399216
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef vector<ll> VI;
typedef vector<VI> VVI;
const ll MOD = 1000000007;
const ll INF = 1000000000000000;
#define REP(i, n) for(int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()

struct edge { int to; int cost; };
vector<edge> G[200000];
vector<ll> d(200000, INF);
void dijkstra(int s) {
	priority_queue<P, vector<P>, greater<P> > que;
	d[s] = 0;
	que.push(P(0, s));
	while (!que.empty()) {
		P p = que.top();
		que.pop();
		int v = p.second;
		if (d[v] < p.first) continue;
		REP(i,G[v].size()) {
			edge e = G[v][i];
			if (d[e.to] > d[v] + e.cost) {
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to], e.to));
			}
		}
	}
}

int main() {
	int n, m; cin >> n >> m;
	REP(i, n) G[i + 1].push_back({ i,0 });
	int a, b, c;
	REP(i, m) {
		cin >> a >> b >> c;
		G[a].push_back({ b,c });
	}
	dijkstra(1);
	if (d[n] == INF)
		cout << -1;
	else
		cout << d[n] << endl;
	return 0;
}

Measured memory_bytes: 11768
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<iomanip>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1e9+7
#define LINF (long long)4e18


int main(){
    int r,D,x;
  cin >> r >> D >> x;
  rep(i,10){
    int ans;
    ans = r * x - D;
    x = ans;
    cout << ans << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <cmath>
#include <numeric>
#include <fstream>
#include <queue>
#include <cstdio>
using namespace std;
#define fol(i,n) for (int i=0;i<n;i++)
#define db(a) cout << a<< endl;
typedef pair <int,int>P;
typedef long long ll;
using namespace std;

int main(){
    int n,k;
    cin >> n>>k;
    int a =k*pow(k-1,n-1);
    cout << a <<endl;
    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define pi 3.141592653589793
#define debug(x) cout << #x << " = " << x << '\n';
using namespace std;





int main() {
//    cout << fixed << setprecision(10);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    string a, b;
    cin >> a >> b;
    cout << b + a;



}

Measured memory_bytes: 256
mo=10**9+7
n,k=map(int,input().split())

def P(n,k,mo):
    rt=1
    for i in range(k):
        rt*=(n-i)
        rt%=mo
    return rt

g=[[] for i in range(1+n)]
v=[0]*(1+n)

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

def dfs(cur):
    q=[]
    q.append(cur)

    while q:
        cur=q.pop()
        v[cur]=1
        c=len(g[cur])-1
        ans[0]*=P(k-2,c,mo)
        
        for nb in g[cur]:
            if v[nb]!=1:
                q.append(nb)
v[1]=1
ans=[P(k,1+len(g[1]),mo)]

for j in g[1]:
    dfs(j)
print(ans[0]%mo)


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

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

  int ans = 0;
  int con = 0;

  for (int i = 0; i < S.size(); i++) {
    if (S.at(i) == 'A' || S.at(i) == 'C' || S.at(i) == 'G' || S.at(i) == 'T') {
      con++;
      ans = max(ans, con);
    }
    else con = 0;
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
using CompLib.Util;
using System;

public class Program
{

    public void Solve()
    {
        var sc = new Scanner();
        int x = sc.NextInt();
        int ans = 1;
        for (int b = 2; b * b <= x; b++)
        {
            int t = b;
            while(t <= x)
            {
                ans = Math.Max(ans, t);
                t *= b;
            }
        }
        Console.WriteLine(ans);

    }

    public static void Main(string[] args) => new Program().Solve();
}

namespace CompLib.Util
{
    using System;
    using System.Linq;
    class Scanner
    {
        private int _index;
        private string[] _line;
        const char separator = ' ';

        public Scanner()
        {
            _index = 0;
            _line = new string[0];
        }

        public string Next()
        {
            while (_index >= _line.Length)
            {
                _line = Console.ReadLine().Split(separator);
                _index = 0;
            }
            return _line[_index++];
        }
        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            _line = Console.ReadLine().Split(separator);
            _index = _line.Length;
            return _line;
        }
        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
    }
}

Measured memory_bytes: 11092
N, M = gets.split.map(&:to_i)                                                   

answer = Array.new(N) { [1, :w] }
answer[0][1] = :r

while s = gets
  x, y = s.split.map(&:to_i)
  answer[x.pred][0] -= 1
  answer[y.pred][0] += 1
  if answer[x.pred][1] == :r
    answer[x.pred][1] = :w if answer[x.pred][0] <= 0
    answer[y.pred][1] = :r
  end
end

p answer.select { |e| 0 < e[0] && e[1] == :r }.length

Measured memory_bytes: 10108
#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int mod=1e9+7;
int a[1000000];
signed main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    int tmp=0;
    for(int i=0;i<n;i++)
        tmp=gcd(tmp,a[i]);
    if(tmp!=1){
        cout<<"not coprime"<<endl;
        return 0;
    }
    set<int>divs;
    for(int i=0;i<n;i++){
        int aa=a[i];
        for(int j=2;j<=1000;j++){
            if(aa<j)
                break;
            if(aa%j==0){
                if(divs.find(j)!=divs.end()){
                    cout<<"setwise coprime"<<endl;
                    return 0;
                }
                divs.insert(aa);
                while(aa%j==0)
                    aa/=j;
            }
        }
        if(aa!=1){
            if(divs.find(aa)!=divs.end()){
                cout<<"setwise coprime"<<endl;
                return 0;
            }
            divs.insert(aa);
        }
    }
    cout<<"pairwise coprime"<<endl;
}

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

int main(){
    int N, K, ans = 0;
    cin >> N >> K;
    vector<int> h(N);
    rep(i,N)    cin >> h[i];
    
    rep(i, N){
        if(h.at(i) >= K)    ans++;
    }

    cout << ans << endl;

    return 0;
}

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

int main(){
  long long N,K;cin>>N>>K;
  long long A[200000];
  
  
  for(int i=0;i<N;i++){
    cin>>A[i];
  }

  for(int i=1;i<N-K+1;i++){
    if(A[i-1]<A[K-1+i]) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;   
  }
}
    

Measured memory_bytes: 5052
#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, n) for (int i = (int)(n-1); i >= 0; i--)
#define sz(x) int(x.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define INF 2e9
#define LINF 1e18
template<class T> inline bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> P;


int main() {
    int n; cin >> n;
    string s; cin >> s;
    vector<int> sum(n+1); //最初Wなら1にする
    sum[0] = 0;
    rep(i, n) {
        if (s[i] == 'W') {
            sum[i+1] = sum[i] + 1;
        }
        else {
            sum[i+1] = sum[i];
        }
    }

    int ans = n;
    rep(i, n+1) {
        if (i == 0) {
            chmin(ans, n-1-(sum[n]-sum[1]));
            continue;
        }
        int left, right;
        left = sum[i-1];
        right = n-i-(sum[n]-sum[i]);
        chmin(ans, left+right);
    }
    cout << ans << endl;
}

Measured memory_bytes: 1796
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
#define ll long long
const ll INF = 1LL<<60;
int main(){//0-index
    int n; cin >> n;
    vector<vector<int> > F(n,vector<int>(14));
    vector<vector<int> > P(n,vector<int>(15));
    rep(i,n){
        rep(j,10){
            cin >> F[i][j];
        }
    }
    rep(i,n){
        rep(j,11){
            cin >> P[i][j];
        }
    }
    ll ans=-INF;
    for(int bit=1;bit<(1<<10);++bit){//bitの2進数表記した時に1である桁に対応した日に自分が営業している
        vector<int> ct(n);
        rep(i,n) ct[i]=0;
        ll res=0;
        rep(i,10){//i番目の時間帯に営業しているか調べる
            if(bit & (1<<i)){//i番目の時間帯に自分の店が営業している時
                rep(j,n){
                    ct[j]+=F[j][i];//j番目の店が時間帯iに営業しているか
                }
            }
        }
        rep(i,n) res += P[i][ct[i]];
        ans = max(ans,res);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#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>;
using v  = vector<int>;
using vv = vector<v>;
const int MOD = 1000000007;

int main(){
    char a;
    cin>>a;
    if(a<'a')
    cout<< "A"<<endl;
    else cout<< "a"<<endl;
    return 0;
}

Measured memory_bytes: 3632
#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    int ans = 0;
    int cnt = 1;
    for (int i=0; i<n; i++) {
        int a;
        cin >> a;
        if (a == cnt)
            cnt++;
        else
            ans++;
    }

    if (ans == n)
        cout << -1 << endl;
    else
        cout << ans << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;
public class Main{
 public static void main(String[] args) {
   double n=0;
   Scanner sc = new Scanner(System.in);
   n=sc.nextInt();
   double x;
   if(n%2==0){
     x=n/2;
   }else{
     x=n/2+0.5;
   }
   int y=(int)x;
   System.out.println(y);
 }
}


Measured memory_bytes: 22228
#include<iostream>
#include<cmath>
#include<bits/stdc++.h>
#include<string.h>
using namespace std;
typedef long long int ll;
const ll maxn=(2*1e5)+2;
ll c;
void dfs(ll node,vector<ll>adj[],ll visited[])
{
    ll i;
    c++;
    visited[node]=1;
    for(i=0;i<adj[node].size();i++)
    {
        if(!visited[adj[node][i]])
        {
            dfs(adj[node][i],adj,visited);
        }
    }

}
int main()
{
    ll n,m;
    cin>>n>>m;
    vector<ll>adj[n+1];
    ll i,x,y;
    for(i=0;i<m;i++)
    {
        cin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    ll visited[n+1];
    for(i=0;i<=n;i++)
    {
        visited[i]=0;
    }
    ll ma=0;
    ll k=0;
    for(i=1;i<=n;i++)
    {
        if(visited[i]==0)
        {
            c=0;
            dfs(i,adj,visited);
            if(c>ma)
                ma=c;
            k++;
        }
    }
    cout<<ma<<"\n";
    cerr<<"\nTime elapsed:"<< 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}


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


#define li          long long int
#define rep(i,to)   for(li i=0;i<((li)(to));i++)
#define repp(i,start,to)    for(li i=(li)(start);i<((li)(to));i++)
#define pb          push_back
#define sz(v)       ((li)(v).size())
#define bgn(v)      ((v).begin())
#define eend(v)     ((v).end())
#define allof(v)    (v).begin(), (v).end()
#define dodp(v,n)       memset(v,(li)n,sizeof(v))
#define bit(n)      (1ll<<(li)(n))
#define mp(a,b)     make_pair(a,b)
#define rin rep(i,n)
#define EPS 1e-12
#define ETOL 1e-8
#define MOD 1000000007
typedef pair<li, li> PI;

#define INF bit(60)

#define DBGP 1


#define idp if(DBGP)
#define F first
#define S second
#define p2(a,b)     idp cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)       idp cout<<a<<"\t"<<b<<"\t"<<c<<endl
#define p4(a,b,c,d)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<endl
#define p5(a,b,c,d,e)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<endl
#define p6(a,b,c,d,e,f)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<endl
#define p7(a,b,c,d,e,f,g)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<endl
#define p8(a,b,c,d,e,f,g,h)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<endl
#define p9(a,b,c,d,e,f,g,h,i)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<endl
#define p10(a,b,c,d,e,f,g,h,i,j)        idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<"\t"<<j<<endl
#define foreach(it,v)   for(__typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it)
#define p2p(x)      idp p2((x).F, (x).S)
#define dump(x,n)   idp{rep(i,n){cout<<x[i]<<" ";}puts("");}
#define dump2(x,n)  idp{rep(i,n){cout<<"["<<x[i].F<<" , "<<x[i].S<<"] ";}puts("");}
#define dumpi(x)    idp{foreach(it, x){cout<<(*it)<<" ";}puts("");}
#define dumpi2(x)   idp{foreach(it, x){cout<<"["<<(it)->F<<" , "<<(it)->S<<"] ";}puts("");}

#define read2d(a,w,h)   rep(i,h)rep(j,w)cin>>a[i][j]
#define dump2d(a,w,h)   rep(i,h){rep(j,w)cout<<a[i][j]<<" ";puts("");}

typedef pair<li, li> PI;


li x[100100];
li pos[2][100100];

int main() {
    li n, k;
    cin >> n >> k;
    li last_neg = -1;
    li first_pos = -1;
    rin{
        cin >> x[i];
        if (x[i] == 0) {
            k--;
        } else if (x[i] < 0) {
            last_neg = i;
        } else if (first_pos < 0) {
            first_pos = i;
        }
        pos[0][i + 1] = pos[1][i + 1] = INF;
    }
    pos[0][0] = 0;
    pos[1][0] = 0;
    rin{
        if (i <= last_neg) {
            pos[0][last_neg - i + 1] = -x[i];
        } else if (x[i] > 0) {
            pos[1][i - first_pos + 1] = x[i];
        }
    }

    //dump(pos[0], n);
    //dump(pos[1], n);

    li res = INF;
    rep(i, k + 1) {
        //p2(i, pos[0][i] + pos[1][k - i] + min(pos[0][i], pos[1][k - i]));
        res = min(res, pos[0][i] + pos[1][k - i] + min(pos[0][i], pos[1][k - i]));
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 2560
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>

using namespace std;

typedef long long ll;

const int K = 63;

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  int tt;
  cin >> tt;
  while (tt--) {
    vector <ll> b(K, -1);
    auto add = [&] (ll x) {
      for (int i = K - 1; i >= 0; --i) {
        if (x & ((ll)1 << i)) {
          if (b[i] == -1) {
            b[i] = x;
            break;
          } else {
            x ^= b[i];
          }
        }
      }
    };
    auto have = [&] (ll x) {
      for (int i = K - 1; i >= 0; --i) {
        if (x & ((ll)1 << i)) {
          if (b[i] != -1) x ^= b[i];
        }
      }
      return x == 0;
    };
    int n;
    cin >> n;
    vector <ll> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    string s;
    cin >> s;
    bool ok = true;
    for (int i = n - 1; i >= 0; --i) {
      if (s[i] == '1') {
        ok &= have(a[i]);
      } else {
        add(a[i]);
      }
    }
    cout << (ok ? 0 : 1) << '\n';
  }
}



Measured memory_bytes: 3580
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <stack>
#include <functional>

// AtCoder
// #include <atcoder/all>
// using namespace atcoder;

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...)
#endif

#define rep_(i, a_, b_, a, b, ...) for (int i = (a), i##_len = (b); i < i##_len; ++i)
#define rep(i, ...) rep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define reprev_(i, a_, b_, a, b, ...) for (int i = (b-1), i##_min = (a); i >= i##_min; --i)
#define reprev(i, ...) reprev_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define all(x) (x).begin(), (x).end()
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; }
#define fls(x) (64 - __builtin_clzll(x))
#define pcnt(x) __builtin_popcountll(x)
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int,int> P;
typedef long double ld;

int main (void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n; cin >> n;
    string s; cin >> s;
    ll a = 0, res = 0;
    rep (i, s.size()) {
        res += -1 + 2 * (s[i] == '(');
        chmax(a, -res);
    }
    rep (i, a) cout << '(';
    cout << s;
    rep (i, a + res) cout << ')';
    cout << "\n";
    /***************************************************/
    /* Submit this code from the browser if using ACL! */
    /***************************************************/
    return 0;
}

Measured memory_bytes: 3652
import java.util.*;
import java.math.*;
public class Main {
	static int x;
	static int ans;
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		String n = in.next();
		int nn = Integer.parseInt(n.substring(n.length() - 1, n.length()));
		String[] ans = {"pon", "pon", "hon", "bon", "hon", "hon", "pon", "hon", "pon", "hon"};
		System.out.println(ans[nn]);
	}
}

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


int32_t main()
{
    int T;
    T = 1;
    while (T--)
    {
        int N,K,tmp,cnt=0;
        cin>>N>>K;
        int gcd = __gcd(N,K);
        for(int i=2; i<=sqrt(gcd); i++)
        {
            if(gcd % i == 0)
            {
                ++cnt;
                gcd /= i;
                while (gcd % i == 0 )
                    gcd /= i;
            }

        }
        if(gcd > 1)
            cnt++;
        cnt++;
        cout<<cnt;


    }
}

Measured memory_bytes: 256
//program luogu.AT2522 Checkpoints
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
const LL inf = 0x7fffffff;

int n,m;
LL a[55],b[55],c[55],d[55];

int pos;
LL minn;

void init() {
	scanf("%d %d",&n,&m);
	for(int i = 1; i <= n; i++)
		scanf("%lld %lld",&a[i],&b[i]);
	for(int i = 1; i <= m; i++)
		scanf("%lld %lld",&c[i],&d[i]);
	return;
}

int main() {
	init();
	for(int i = 1; i <= n; i++) {
		minn = inf;
		pos = 0;
		for(int j = 1; j <= m; j++) {
			LL dis = abs(a[i]-c[j]) + abs(b[i]-d[j]);
			if( dis < minn ) {
				minn = dis;
				pos = j;
			}
		}
		printf("%d\n",pos);
	}
	return 0;
}
/**

2 2
2 0
0 0
-1 0
1 0

2
1

**/



/**

3 4
10 10
-10 -10
3 3
1 2
2 3
3 5
3 5

3
1
2

**/



/**

5 5
-100000000 -100000000
-100000000 100000000
100000000 -100000000
100000000 100000000
0 0
0 0
100000000 100000000
100000000 -100000000
-100000000 100000000
-100000000 -100000000

5
4
3
2
1

**/

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
using namespace std;

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

    switch (n %= 10) {
    case 2: case 4: case 5: case 7: case 9:
        cout << "hon" << endl;
        break;
    case 0: case 1: case 6: case 8:
        cout << "pon" << endl;
        break;
    case 3:
        cout << "bon" << endl;
        break;
    }
}


Measured memory_bytes: 3620
#include <iostream>
#include <string.h>
#include <vector>

using namespace std;

#define pb push_back
#define mp make_pair
#define ll long long
#define ull unsigned ll
#define db double
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define PII pair<int, int>

int n,k,a,b;
int dis[2010];
int q[2010];
int pq;
vector<int> g[2010];

void bfs() {
    for (int i=0;i<pq;i++) {
        int u=q[i];
        int dv=dis[u]+2;
        if (dv>k) continue;
        for (int j=0;j<g[u].size();j++) {
            int v=g[u][j];
            if (dis[v]==INF) {
                q[pq]=v;
                pq++;
                dis[v]=dv;
            }
        }
    }
}

int work1(int u) {
    memset(dis,INF,sizeof(dis));
    memset(q,0,sizeof(q));
    q[0]=u;
    dis[u]=0;
    pq=1;
    bfs();
    int cnt=0;
    for (int i=1;i<=n;i++) if (dis[i]>k) cnt++;
    return cnt;
}

int work2(int u,int v) {
    memset(dis,INF,sizeof(dis));
    memset(q,0,sizeof(q));
    q[0]=u;
    q[1]=v;
    dis[u]=dis[v]=1;
    pq=2;
    bfs();
    int cnt=0;
    for (int i=1;i<=n;i++) if (dis[i]>k) cnt++;
    return cnt;
}

int main() {
    scanf("%d%d",&n,&k);
    for (int i=0;i<n;i++) {
        scanf("%d%d",&a,&b);
        g[a].pb(b);
        g[b].pb(a);
    }
    int ans=INF;
    for (int i=1;i<=n;i++) {
        int tmp=work1(i);
        ans=min(ans,tmp);
    }
    for (int i=1;i<=n;i++) {
        for (int j=0;j<g[i].size();j++) {
            int v=g[i][j];
            if (i<v) {
                int tmp=work2(i,v);
                ans=min(ans,tmp);
            }
        }
    }
    printf("%d\n",ans);
}

Measured memory_bytes: 384
#include <cmath>
#include <iostream>
using namespace std;
using ll = long long;

int main(int argc, char const *argv[]) {
  ll x;
  cin >> x;
  ll money = 100;
  int year = 0;
  while (1) {
    if (money < x) {
      money = money * 1.01;
      year++;
    } else {
      break;
    }
  }
  cout << year << endl;
  return 0;
}


Measured memory_bytes: 3616
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <sstream>
#include <iostream>
#include <time.h>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <string.h>
#define sf scanf
#define pf printf
#define lf double
#define ll long long
#define p123 printf("123\n");
#define pn printf("\n");
#define pk printf(" ");
#define p(n) printf("%d",n);
#define pln(n) printf("%d\n",n);
#define s(n) scanf("%d",&n);
#define ss(n) scanf("%s",n);
#define ps(n) printf("%s",n);
#define sld(n) scanf("%lld",&n);
#define pld(n) printf("%lld",n);
#define slf(n) scanf("%lf",&n);
#define plf(n) printf("%lf",n);
#define sc(n) scanf("%c",&n);
#define pc(n) printf("%c",n);
#define gc getchar();
#define re(n,a) memset(n,a,sizeof(n));
#define len(a) strlen(a)
using namespace std;
//https://codeforces.com/contest/1228/problems
//https://codeforces.com/contest/1228/submit
int a[100000];
int b[105][105];
int main() {
    int h,w;
    int n;
    s(h) s(w) s(n)
    for(int i = 1; i <= n; i ++){
        s(a[i])
    }
    int flag = 1;
    for(int i = 1; i <= h/2; i ++){
        for(int j = 1; j <= w; j ++){
            if(a[flag] != 0){
                b[i*2-1][j] = flag;
                a[flag] --;
            }else{
                flag ++;
                b[i*2-1][j] = flag;
                a[flag] --;
            }
        }
        for(int j = w; j >= 1; j --){
            if(a[flag] != 0){
                b[i*2][j] = flag;
                a[flag] --;
            }else{
                flag ++;
                b[i*2][j] = flag;
                a[flag] --;
            }
        }
    }
    if(h % 2 == 1){
        for(int j = 1; j <= w; j ++){
            if(a[flag] != 0){
                b[h][j] = flag;
                a[flag] --;
            }else{
                flag ++;
                b[h][j] = flag;
                a[flag] --;
            }
        }
    }
    for(int i = 1; i <= h; i ++){
        for(int j = 1; j < w; j ++){
            p(b[i][j]) pk
        }
        p(b[i][w])
        pn
    }
    return 0;
}
/*

2
3 1 2
4 1 10


*/



Measured memory_bytes: 504
#include<stdio.h>
#include<math.h>
int main(){
    int n, t, hm, d=0, c=1, i;
    scanf("%d%d", &n, &t); //input the number of test and target number
    for(i = 0;i < n ; i++){
        scanf("%d", &hm);
        if(hm<=t){
            d = d+hm;
            if(d<=t)
            c++;
        }
    }
    printf("%d\n", c);
    return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<string>
#include<cstdlib>
#include<vector>
#include<algorithm>
#include<functional>

#define REP(i,n) for(int i=0;i<n;i++)
#define ll long long int

using namespace std;

int to_int(string s) {
  return atoi(s.c_str());
}

ll p = 1000000007;

ll mu[100000];
ll a[100000];
ll ab[100000];
ll abc[100000];

int main() {
  int t;
  string s;
  cin >> s;
  t = s.length();
  REP(i,t) {
    if(i == 0) {
      if(s[i] == 'A') {
        a[i] = 1;
        mu[i] = 1;
      } else if(s[i] == '?') {
        a[i] = 1;
        mu[i] = 3;
      } else {
        mu[i] = 1;
      }
      ab[i] = 0;
      abc[i] = 0;
      continue;
    }
    if(s[i] == 'A') {
      mu[i] = mu[i-1];
      a[i] = (a[i-1] + mu[i-1])%p;
      ab[i] = ab[i-1];
      abc[i] = abc[i-1];
    }
    if(s[i] == 'B') {
      mu[i] = mu[i-1];
      a[i] = a[i-1];
      ab[i] = (ab[i-1] + a[i-1])%p;
      abc[i] = abc[i-1];
    }
    if(s[i] == 'C') {
      mu[i] = mu[i-1];
      a[i] = a[i-1];
      ab[i] = ab[i-1];
      abc[i] = (abc[i-1] + ab[i-1])%p;
    }
    if(s[i] == '?') {
      mu[i] = (3*mu[i-1])%p;
      a[i] = (mu[i-1] + 3*a[i-1])%p;
      ab[i] = (a[i-1] + 3*ab[i-1])%p;
      abc[i] = (ab[i-1] + 3*abc[i-1])%p;
    }
  }
  cout << abc[t-1] << endl;
}


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

int main(){
  int n, count = 0;
  cin >> n;

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

  for(int i = 0; i < n - 1; i++){
    int min = i;
    for(int j = i + 1; j < n; j++)
      if(a[j] < a[min]) min = j;      

    if(min != i){
      int tmp = a[i];
      a[i] = a[min];
      a[min] = tmp;
      count++;
    }    
  }

  for(int i = 0; i < n-1; i++) cout << a[i] << " ";
  cout << a[n-1] << endl;
  cout << count << endl;
  
  return 0;
}

Measured memory_bytes: 3088
h,n = map(int,input().split())
l = []
k = 0
for i in range(n):
    a,b = map(int,input().split())
    l.append([a,b])
    k += a
ans = 0
i = 0
dp = [0 for i in range(h+1)]
for i in range(n):
    a,b = l[i]
    for j in range(h):
        if j+a <= h:
            if j == 0:
                if dp[j+a] == 0:
                    dp[j+a] = b
                else:
                    dp[j+a] = min(b,dp[j+a])
            else:
                if dp[j] != 0:
                    if dp[j+a] == 0:
                        dp[j+a] = dp[j] + b
                    else:
                        dp[j+a] = min(dp[j]+b,dp[j+a])
        else:
            if dp[j] != 0:
                if dp[h] == 0:
                    dp[h] = dp[j]+b
                else:
                    dp[h] = min(dp[h],dp[j]+b)
            else:
                if j == 0:
                    if dp[h] == 0:
                        dp[h] = dp[j]+b
                    else:
                        dp[h] = min(dp[h],dp[j]+b)
print(dp[h])

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

int main(){
  
 int a,b,c = 0;
  
  cin >> a >> b >> c;
  
  if (c-(a-b) > 0){
    cout << c - (a-b) << endl;
  } else{
    cout << "0" << endl; 
  }
  
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define ll int64_t
#define _GLIBCXX_DEBUG
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
int main(){
  int n,m;
  cin >> n >> m;
  vector<int> a(m),b(m);
  vector<pair<int,int>> p(m);
  rep(i,m){
    cin >> a.at(i) >> b.at(i);
    p.at(i)=make_pair(b.at(i),a.at(i));
  }
  sort(all(p));
  int t,c;
  t=-1;
  rep(i,m){
    if(t<=p.at(i).second){
      c++;
      t=p.at(i).first;
    }
  }
  cout << c << endl;
}
  

Measured memory_bytes: 1792