akhauriyash/Code-Regression huggingface dataset:
import java.io.IOException;
import java.util.Scanner;

/**
 * Created on 2017/10/25 7:03.
 */
public class Main {
    public static void main(String[] args) throws IOException {
        // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Scanner sc = new Scanner(System.in);

        while (sc.hasNextInt()) {
            int N = sc.nextInt();
            int ans = 0;
            for (int i = 0; i < N; i++) {
                int l = sc.nextInt();
                int r = sc.nextInt();
                ans += (r - l) + 1;
            }
            System.out.println(ans);
        }
    }
}

Measured memory_bytes: 26064
import numpy as np

H, N = map(int, input().split())

A = []
B = []
for i in range(N):
	a, b = list(map(int, input().split()))
	A.append(a)
	B.append(b)

A = np.array(A)
B = np.array(B)

dp = np.full((H+1), np.inf)
dp[0] = 0

def solve():
	for i in range(1, H + 1):
		dp[i] = np.amin(dp[np.maximum(i - A, 0)] + B)
	return int(dp[H])

print(solve())

Measured memory_bytes: 14540
#include<iostream>
#include<string>
#include<algorithm>
#include<utility>
#include<cmath>
#include<vector>
#define ll long long int
using namespace std;
int main(void) {
  int n;
  vector<int> v;
  int x;
  int ans=0;
  cin>>n;
  for(int i=0; i<n; i++) {
    cin>>x;
    v.push_back(x);
  }
  sort(v.begin(), v.end());
  x=v[0];
  for(auto it=v.begin()+1; it!=v.end(); it++) {
    ans+=abs(x-*it);
    x=*it;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int T = sc.nextInt();

		int ans = 100000007;

		for (int i = 0; i < n; i++) {
			int c = sc.nextInt();
			int t = sc.nextInt();

			if (t <= T) {
				if (c < ans) {
					ans = c;
				}
			}

		}
		if (ans > 1000) {
			System.out.println("TLE");

		} else {

			System.out.println(ans);
		}

	}
}


Measured memory_bytes: 22228
n = int(input())
a = list(map(int,input().split()))
a = [str(bin(i)) for i in a]
cnt = 1
flg = False
while True:
    for i in a:
        if i[-cnt] == '1':
            flg = True
            break
    if flg == True:
        break
    cnt += 1
print(cnt-1)

Measured memory_bytes: 3060
#include<cstdio>
int main() {
	int a[4];
	for (int i = 0; i < 4; i++)scanf("%d", &a[i]);
	printf("%d", (a[0] < a[1] ? a[0] : a[1]) + (a[2] < a[3] ? a[2] : a[3]));
	return 0;
}

Measured memory_bytes: 128
N = int(input())
A = list(map(int, input().split()))

dp = [0]*(N)
dp[0] = 1000

for i in range(1,N):
    dp[i] = dp[i-1]
    for j in range(i):
        dp[i] = max(dp[i], (dp[j]//A[j])*A[i]+dp[j]%A[j])
ans = 0
for i in range(N):
    ans = max(ans, dp[i])
print(ans)

Measured memory_bytes: 64268
#include<stdio.h>
int main()
{
    int n,i,j;
    scanf("%d",&n);
    int a[n],b[n];
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    for(i=i-1;i>=0;i=i-2)
        printf("%d ",a[i]);
    if(i%2) i=0;
    else i=1;
    for(;i<n;i=i+2)
        printf("%d ",a[i]);
    return 0;
}

Measured memory_bytes: 2816
#include <cstdio>
#define N 105

int n, k;
int a[N];

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1, x; i <= k; ++i) {
        scanf("%d", &x);
        for (int j = 1, t; j <= x; ++j) {
            scanf("%d", &t);
            a[t] = 1;
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) ans += a[i];
    printf("%d\n", n - ans);
    return 0;
}


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

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

constexpr int MAX_N = 1e2;
constexpr int MAX_V = 1e3;
constexpr int INF = 1e9+9;

int dp[MAX_N+1][MAX_N*MAX_V+1];

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

  fill_n(dp[0], (MAX_N+1)*(MAX_N * MAX_V+1), INF);
  dp[0][0] = 0;
  for (int i{}; i < N; ++i) {
    int w, v; cin >> w >> v;
    for (int j{}; j <= N * MAX_V; ++j) {
      chmin(dp[i+1][j], dp[i][j]);
      if (j >= v) {
        chmin(dp[i+1][j], dp[i][j - v] + w);
      }
    }
  }

  for (int j{N*MAX_V}; j >= 0; --j) {
    if (dp[N][j] <= W) {
      cout << j << endl;
      break;
    }
  }

  return 0;
}


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

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << setprecision(20);
  int n, m;
  cin >> n >> m;
  int l_max = 1;
  int r_min = n;
  rep(i, m) {
    int l, r;
    cin >> l >> r;
    l_max = max(l, l_max);
    r_min = min(r, r_min);
  }
  if (r_min < l_max) {
    cout << 0 << endl;
  } else {
    cout << r_min - l_max + 1 << endl; 
  }
  return 0;
}


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

using namespace std;

#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpii;
typedef vector<pair<ll, ll>> vpll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template<class T>
void print(vector<T>& V, bool spaced = true) {
    string space;
    spaced ? space = " " : space = "";
    for(int i = 0; i < V.size(); i++) {
        cout<< V[i] << space;
    }cout<< '\n';
}

template<class T>
void printendl(vector<T>& V) {
    for(int i = 0; i < V.size(); i++) {
        cout<< V[i] << '\n';
    }
}

template<class T>
T gcd(T a, T b) {
    T r;
    while (b != 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

template <class T>
T lcm (T a, T b) {
    return a / gcd(a, b) * b;
}

template<class T>
T Max(T a, T b) {
    return (a < b) ? b : a;
}

template<class T>
T Min(T a, T b) {
    return (a < b) ? a : b;
}

//str

bool isPalindrome(string str){
    
    int length = str.length();
 
    for (int i = 0; i < (length / 2); i++)
        if (str[i] != str[length - 1 - i])
            return false;
 
    return true;    
}

void reverseStr(string& str) 
{ 
    int n = str.length(); 
    for (int i = 0; i < n / 2; i++) 
        swap(str[i], str[n - i - 1]); 
}
 

//Read through the messages at the end when you're done

int dp[100000][3];
int cost[100000][3];

int main() {

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

    memset(dp, -1, sizeof(dp));
    int n; cin>> n;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < 3; ++j) cin>> cost[i][j];
    }

    dp[n-1][0] = cost[n-1][0];
    dp[n-1][1] = cost[n-1][1];
    dp[n-1][2] = cost[n-1][2];

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

    
    

    return 0;
}

    //Use long long da5eel rabbak!
    //Dont use endl;
    //DONT SUBMIT IZA UR NOT SURE WALLAHI BTENDAM
    //Dear Amine, just because it worked for the test cases doesnt necessarily mean it is correct.
    //Dear Amine, try it on ur own test cases iza ur not SURE
    //In case u didnt use long long, CHECK FOR POTENTIAL OVERFLOWS
    //DONT FORGET TO MOD EVERYTHING IZA U NEED TO MOD



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

long long int dp[105][100005];

int main() {
	int n,w;
	cin>>n>>w;
	int ar[n][2];
	for(int i=0;i<n;i++)
		cin>>ar[i][0]>>ar[i][1];
	
	for(int i=0;i<=w-ar[0][0];i++)
		dp[0][i]=ar[0][1];
	
	for(int i=0;i<n-1;i++)
		for(int j=0;j<=w;j++){
			if(j>=ar[i+1][0]) /*cout<<i<<' '<<j<<' '<<dp[i][j-ar[i+1][0]]<<' '<<ar[i+1][1]<<' '<<dp[i][j]<<'\n',*/dp[i+1][j-ar[i+1][0]]=max(dp[i+1][j-ar[i+1][0]],dp[i][j]+ar[i+1][1]);
			dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
		}
	
	//for(int i=0;i<n;cout<<'\n',i++)
	//	for(int j=0;j<=w;j++)
	//		cout<<dp[i][j]<<' ';
	
	long long int maxn=0;
	for(int i=0;i<=w;i++)
		maxn=max(dp[n-1][i],maxn);
	cout<<maxn<<'\n';
}

Measured memory_bytes: 80128
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.PrintWriter;
import java.io.IOException;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws IOException{
        Scanner reader = null;
        PrintWriter writer = null;
        
        try {
            reader =new Scanner(System.in);
            writer = new PrintWriter(System.out);
            
            writer.println(48 - reader.nextInt());
            
        }finally{
            if(reader != null){
                reader.close();
            }
            if(writer != null){
                writer.close();
            }
        }

    }
}

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

using namespace std;

typedef long long ll;

int main(){
        int N;
        cin>>N;
        vector <ll> t(N), a(N);
        for(int i=0;i<N;i++){
                cin>>t[i]>>a[i];
        }
        ll tnow=1, anow=1;
        for(int i=0;i<N;i++){
                ll tn=tnow/t[i];
                if(tnow%t[i]!=0){
                        tn++;
                }
                ll an=anow/a[i];
                if(anow%a[i]!=0){
                        an++;
                }
                ll n=max(tn, an);
                tnow=n*t[i], anow=n*a[i];
        }
        cout<<tnow+anow<<endl;
        return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mt make_tuple
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
//typedef tuple<ll,ll,ll,ll> tp;
//typedef vector<tp> vt;
typedef vector<vd> vvd;
typedef pair<int,pii> pip;
typedef vector<pip>vip;
const double PI=acos(-1);
const double EPS=1e-7;
const int inf=1e9;
const ll INF=2e18;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int main(){
	string out[]={
		{".,!? "},
		{"abc"},
		{"def"},
		{"ghi"},
		{"jkl"},
		{"mno"},
		{"pqrs"},
		{"tuv"},
		{"wxyz"}
	};
	int n;
	cin>>n;
	while(n--){
		string s;
		cin>>s;
		int now=-1,co=0;
		s+="0";
		rep(i,s.size()){
			if(s[i]=='0'){
				co--;
				if(now+1)cout<<out[now][co%out[now].size()];
				now=-1;
				co=0;
			}else{
				now=s[i]-'1';
				co++;
			}
		}
		cout<<endl;
	}
}

Measured memory_bytes: 3144
n = int(input())
a = [int(input()) for _ in range(n)]

tNum = max(a)
sNum = sorted(a, reverse=True)[1]

if a.count(tNum) > 1:
  for _ in range(n):
    print(tNum)
  exit()

for i in a:
  if i == tNum:
    print(sNum)
    continue
  print(tNum)

Measured memory_bytes: 13316
n,x,y=map(int,input().split())

#最短距離が１の時２の時、、、という風に実験しても途方に暮れるだけだった
#i,j固定して最短距離がどう表せるかを考える
def min_route_count(i,j):
  return min(abs(j-i),abs(j-y)+1+abs(x-i))

ans_list=[0]*(n-1)
for i in range(1,n):
  for j in range(i+1,n+1):
    ans_list[min_route_count(i,j)-1]+=1
    
for t in range(n-1):
  print(ans_list[t])


Measured memory_bytes: 75120
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
#define vi vector<int>
#define vll vector<ll>
#define pll pair<ll,ll>
#define pii pair<int,int>
#define pb  push_back
#define mp  make_pair
#define NODE 1000005
#define NINF INT_MIN

vll graph[NODE];
bool vis[NODE];
bool wset[NODE];
int wss;
bool gset[NODE];
bool bset[NODE];
void dfs(int node,int dp[]) 
{ 
    // Mark as visited 
    vis[node] = true; 
  
    // Traverse for all its children 
    for (auto v:graph[node]) { 
  
        // If not visited 
        if (!vis[v]) 
            dfs(v,dp); 
  
        // Store the max of the paths
        dp[node] = max(dp[node], 1 + dp[v]); 
    } 
}
  
// Function that returns the longest path 
int findLongestPath(int n) 
{ 
    // Dp array 
    int dp[n + 1]; 
    memset(dp, 0, sizeof dp);
  
    // Call DFS for every unvisited vertex 
    for (int i = 1; i <= n; i++) { 
        if (!vis[i]) 
            dfs(i,dp); 
    } 
  
    int ans = 0; 
  
    // Traverse and find the maximum of all dp[i] 
    for (int i = 1; i <= n; i++) { 
        ans = max(ans, dp[i]); 
    } 
    return ans; 
}

bool dfs(int curr) {
   //moving curr to white set to grey set.
   wset[curr]=false;
   wss--;
   gset[curr]=true;

   for(auto v:graph[curr]) {

         if(bset[v]==true)
            continue;    //if the vertices are in the black set
         if(gset[v]==true)
            return true;    //it is a cycle
         if(dfs(v))
            return true;    //cycle found
   }

   //moving v to grey set to black set.
   gset[curr]=false;
   bset[curr]=true;
   return false;
}

bool hasCycle(int k) {
	wss=0;
   for(int i = 1; i<=k; i++){
      wss++;
      wset[i]=true;   //initially add all node into the white set
   }

   while(wss > 0) {
   	// cout<<1<<endl;
      for(int current = 1; current <= k; current++) {
         if(wset[current]==true)
            if(dfs(current))
               return true;
      }
   }
   return false;
}

int main(){
	// #ifndef ONLINE_JUDGE
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
	// #endif
	ll n;
	cin>>n;
	map< pair<ll,ll> , ll> m;
	ll k=1;
	for(ll i=1;i<=n;++i){
		for(ll j=i+1;j<=n;++j){
			m[mp(j,i)]=k++;
		}
	}
	// for(auto val: m){
	// 	for(auto p :val.first)
	// 		cout<<p<<" ";
	// 	cout<<":";
	// 	cout<<val.second<<endl;
	// }
	pair<ll,ll> s,t;
	for(ll i=1;i<=n;++i){
		ll val;
		scanf("%d",&val);
		s=mp(max(i,val),min(i,val));
		for(ll j=1;j<n-1;++j){
			scanf("%d",&val);
			t=mp(max(i,val),min(i,val));
			graph[m[s]].pb(m[t]);
			s=t;
		}
	}
	// cout<<"here"<<endl;
	if(hasCycle(k))
		printf("-1\n");
	else{
		// cout<<1<<endl;
		printf("%d",findLongestPath(k)+1);
	}
}

Measured memory_bytes: 75520
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define DUMP(x)  cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define IFOR(i, m, n) for(ll i = n - 1; i >= m; i-- )
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define FOREACH(x,a) for(auto& (x) : (a) )
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) ll(x.size())

int main(){
  ll N,K; cin >> N >> K;
  //(x,y)が白　と　(x,y+K)が黒は同値
  vector<ll> x(N), y(N);
  REP(i,N){
    char t;
    cin >> x[i] >> y[i] >> t;
    if(t=='W') y[i] += K;
    x[i] %= 2*K;
    y[i] %= 2*K;
  }
  ll ans = 0;
  //(+3K,+3K)平行移動
  vector<vector<int>> sum(5*K+1, vector<int>(5*K+1,0));
  //左下(i,j)として加算
  auto add_cnt = [&](ll i, ll j){
    if(i>=5*K || j>=5*K) return;
    ll a = min(i+K,5*K);
    ll b = min(j+K,5*K);
    sum[i][j]++;
    sum[a][b]++;
    sum[i][b]--;
    sum[a][j]--;
  };
  REP(i,N){
    REP(j,3) REP(k,3){
      add_cnt(x[i]+(2*j+1)*K, y[i]+(2*k+1)*K);
    }
    REP(j,2)REP(k,2){
      add_cnt(x[i]+(2*j+2)*K,y[i]+(2*k+2)*K);
    }
  }
  //累積和とる
  REP(i,5*K+1) REP(j,5*K){
    sum[i][j+1] += sum[i][j];
  }
  REP(j,5*K+1)REP(i,5*K){
    sum[i+1][j] += sum[i][j];
  }
  REP(i,5*K+1) REP(j,5*K+1){
    ans = max(ans,(ll)sum[i][j]);
  }
  cout << ans << endl;
}


Measured memory_bytes: 99712
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define Rep(i,n) for(intl i=0,nn=(intl)(n);i<nn;++i)
#define Rep1(i,n) for(intl i=1,nn=(intl)(n)+1;i<nn;++i)
#define vec vector
#define fi first
#define se second
#define pub push_back
#define pob pop_back
#define SortA(v) sort(v.begin(), v.end())
#define SortD(v) sort(v.rbegin(),v.rend())
#define All(a) (a).begin(),(a).end()
#define Input(a) for(intl ii=0,nn=(intl)(a.size());ii<nn;ii++){cin>>(a).at(ii);}
#define Input2(a,b) for(intl ii=0,nn=(intl)(a.size());ii<nn;ii++){cin>>(a).at(ii);cin>>(b).at(ii);}
#define mp make_pair
#define mt make_tuple
using intl = int64_t;
using vi = vec<intl>;
using vvi = vec<vi>;
using pi = pair<intl,intl>;
using vpi = vec<pi>;
using si = set<intl>;
using vsi = vec<si>;
using mii = map<intl,intl>;
using vmii = vec<mii>;
vec<intl> dx = {0, 1, 0, -1, 1, 1, -1, -1};
vec<intl> dy = {1, 0, -1, 0, 1, -1, 1, -1};
constexpr intl INF = 9223372036854775807;



int main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  intl n;
  cin >>n;
  vi N(10000001);
  Rep1(i,10000000){
    N[i]=i*2;
  }
  for(intl i = 2;i*i <= 10000000ll; i++){
    for(intl j = i*2; j <= 10000000ll; j+=i){
      //if(j == i*i){ N[j] +=j;continue;}
      N[j] +=(j/i <= 3162 || j == i*i)?j:j*2;
    }
  }
  intl sum =0;
  Rep1(i,n){
    sum += N[i];
  }
  cout <<sum-1;//<<endl;
  //cout <<sum-1-838627288460105ll;
}
        

Measured memory_bytes: 81344
import queue 
N = int(input())
tree = [[]for _ in range(N+1)]
for i in range(1,N):
    a,b = map(int,input().split())
    tree[a].append( [b,i])
    tree[b].append([a,i])
 
que = queue.Queue()
node = [-1]*(N+1)
edge = [-1]*N
que.put(1)
node[1] = 1
maxi = 1
start = 0
color = [[] for _ in range(N+1)]
node[1] = 0
while(True):
    if que.empty():
        break
    before = start
    start = que.get()
    col =1
    for i in tree[start]:
        
        if node[i[0]] == -1 :
            que.put(i[0])
        if edge[i[1]] == -1:
            if col == node[start]:
                col += 1
            edge[i[1]] = col
            node[i[0]] = col
            if col > maxi:
                maxi = col
            col +=1
            
print(maxi)
for i in edge[1:]:
    print(i)

Measured memory_bytes: 54772
import java.util.*;
import java.lang.Math;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
      	long nums[] = new long[4];
      	long ans;
      	long lstack;
  
      	for(int i = 0;i < 4;i++) nums[i] = sc.nextLong();
      	ans = nums[0] * nums[2];
      	for(int i = 0;i < 2;i++){
          for(int j = 0;j < 2;j++){
      		lstack = nums[i]*nums[2+j];
            if(lstack > ans) ans = lstack;
          }
        }
           
      	System.out.println(ans);
        
	}
}


Measured memory_bytes: 35692
def calculate():
    s = input()

    n0 = s.count("0")
    n1 = s.count("1")

    if n0 == n1:
        print(n0*2)
    elif n0 > n1:
        print(n1 * 2)
    else:
        print(n0 * 2)



calculate()

Measured memory_bytes: 3188
#include <bits/stdc++.h> 
 
using namespace std;
 
 template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef pair<long, long> PLL;
typedef long long LL;
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define PB emplace_back
#define MP make_pair 
#define SZ(a) int((a).size())
//repetition
//------------------------------------------
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())
//constant
//--------------------------------------------
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

const int MAX_V=1e5;
const int MAX_M=2e5;
const int INF=INT_MAX;

typedef pair<int,int> PS;
struct edge{PS to;long cost;};
typedef pair<long,PS> P;//firstは最短距離,secondは頂点番号

int V;
map<PS,vector<edge>> G;
map<PS,long>d;

void dijkstra(PS 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();//仮の最短距離が短い順に取り出す
        auto v=p.second;
        if(d.find(v)!=d.end()&&d[v]<p.first)continue;
        if(G.find(v)!=G.end())REP(i,G[v].size()){
            edge e=G[v][i];
            if(d.find(e.to)==d.end()||d[e.to]>d[v]+e.cost){
                d[e.to]=d[v]+e.cost;
                que.push(P(d[e.to],e.to));//仮の最短距離と頂点の組を更新が行われる度に追加していく
            }
        }
    }
}

vector<int>eki[MAX_M];
int main(){
    LL N,M;cin>>N>>M;
    REP(i,M){
        int p,q,c;
        cin>>p>>q>>c;
        p--;q--;c--;
        G[PS{q,c}].PB(edge{PS{p,c},0});
        G[PS{p,c}].PB(edge{PS{q,c},0});
        G[PS{p,c}].PB(edge{PS{p,-1},0});
        G[PS{q,c}].PB(edge{PS{q,-1},0});
        eki[p].PB(c);eki[q].PB(c);
    }
    REP(i,N)REP(j,SZ(eki[i]))G[PS{i,-1}].PB(edge{PS{i,eki[i][j]},1});
    dijkstra(PS{0,-1});
    if(d.find(PS{N-1,-1})==d.end()){
        cout<<-1<<endl;
    }else{
        cout<<d[PS{N-1,-1}]<<endl;
    }
    return 0;
}
//出るタイミングで加算
//

Measured memory_bytes: 109680
N = input()

if(len(N) == 0):
  print(int(N))
else:
  cand = str(int(N[0])-1) + '9' * (len(N) - 1)
  cand_int = eval("+".join(cand))
  N_int = eval("+".join(N))
  print( max(cand_int, N_int) )

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
 
int main() {  
    int N,A,x;
    cin >> N;
    cin >> A;
    x = N % 500;
    if (A >= x) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 3584
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

int main() {
int i, a[1000]={0, 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
scanf("%d", &i);
printf("%d", a[i]);


    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using lint = int64_t;
// cout << "\t" << endl;

int solve(int p, int q, int n, int x, int y);

int main() {
  int n, x, y;
  cin >> n >> x >> y;
  x--;
  y--;
  vector<int> ans(n - 1, 0);
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      int d = solve(i, j, n, x, y);
      ans.at(--d)++;
    }
  }

  for (int i = 0; i < n - 1; i++) {
    cout << ans.at(i) << endl;
  }
}

int solve(int p, int q, int n, int x, int y) {
  int d1, d2;
  d1 = q - p;
  if (abs(p - x) <= abs(p - y)) {
    d2 = abs(p - x) + 1 + abs(q - y);
  } else {
    d2 = abs(p - y) + 1 + abs(q - x);
  }
  return min(d1, d2);
}

Measured memory_bytes: 256
def touSum(a,l):
    return int(((l-a+1)*(a+l))/2)

N,K = map(int,input().split())
maxSum = touSum(1,N)
#print(maxSum)
con = 0
for i in range(K,N+1+1):
    #print(str(i)+":"+str(touSum(1,i-1))+":"+str(touSum((1+N)-i,N)))
    if touSum(1,i-1)>maxSum:
        print(con)
        break
    else:
        con += touSum((1+N)-i,N) -touSum(1,i-1)+1
print(con%(10**9+7))

Measured memory_bytes: 9212
//税
using System;

namespace tst
{
    
    class Program
    {
        public static void Main()
        {
            //string読み込み
            string day=Console.ReadLine();
            switch (day)
            {
                case "SUN":
                    Console.WriteLine(7);
                    break;
                case "MON":
                    Console.WriteLine(6);
                    break;
                case "TUE":
                    Console.WriteLine(5);
                    break;
                case "WED":
                    Console.WriteLine(4);
                    break;
                case "THU":
                    Console.WriteLine(3);
                    break;
                case "FRI":
                    Console.WriteLine(2);
                    break;
                case "SAT":
                    Console.WriteLine(1);
                    break;
            }
        }

    }
}

Measured memory_bytes: 11220
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());

    if (K <= (N + 1) / 2) {
      System.out.println("YES");
    } else {
      System.out.println("NO");
    }

  }
}

Measured memory_bytes: 21844
/**
 * File    : C.cpp
 * Author  : Kazune Takahashi
 * Created : 2/9/2019, 9:06:09 PM
 * Powered by Visual Studio Code
 */

#include <iostream>
#include <iomanip>   // << fixed << setprecision(xxx)
#include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ;
#include <vector>
#include <string> // to_string(nnn) // substr(m, n) // stoi(nnn)
#include <complex>
#include <tuple>
#include <queue>
#include <stack>
#include <map> // if (M.find(key) != M.end()) { }
#include <set>
#include <functional>
#include <random> // auto rd = bind(uniform_int_distribution<int>(0, 9), mt19937(19920725));
#include <chrono> // std::chrono::system_clock::time_point start_time, end_time;
// start = std::chrono::system_clock::now();
// double elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end_time-start_time).count();
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;

#define DEBUG 0 // change 0 -> 1 if we need debug.

typedef long long ll;

// const int dx[4] = {1, 0, -1, 0};
// const int dy[4] = {0, 1, 0, -1};

// const int C = 1e6+10;
// const ll M = 1000000007;

ll K, A, B;

int main()
{
  cin >> K >> A >> B;
  if (B - A <= 2)
  {
    cout << K + 1 << endl;
    return 0;
  }
  ll x = (K - (A - 1)) / 2;
  cerr << "x = " << x << endl;
  ll ans = 0;
  if (x <= 0)
  {
    cout << K + 1 << endl;
    return 0;
  }
  if (A - 1 + 2 * x < K)
  {
    ans++;
  }
  ans += A + x * (B - A);
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
  char a,b;
  bool a1,b1;
  cin >> a >> b ;
  if(a == 'H') a1 = true;
  else a1 = false ;
  if(b == 'H') b1 = true;
  else b1 = false ;

  if(a1^b1) cout << 'D' << endl;
  else cout << 'H' << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<iomanip>
typedef long long int ll;
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define REP(i,n) for (int i=0;i<(n);i++)
#define EREP(i,n) for (int i=1;i<=(n);i++)
#define ALL(a) (a).begin(),(a).end()
#define EVEL 1

#ifndef EVEL
#define DEB(X) cout << #X << ":" <<X<<" " ;
#define TF(f) f ? cout<<"true  " : cout<<"false ";
#define END cout<<"\n";
#else
#define DEB(X) {}
#define TF(f) {}
#define END {}
#endif
const int MOD = 1000000007;
const int INF = 2000000000;

    int A,B,C;
    int N,M,K,X,Y,W,H;
    int ans;
    string S;
    int temp[100]={0};
    bool f=false;
    bool fir=true;

int main(){
    cin>>A>>B;
    if(A>B){
        N=A;
        A=B;
        B=N;
    }
    if(A==B)f=true;
    else if(A==2||B==2)f=false;
    else if(A==4||A==6||A==9||A==11){
        if(B==4||B==6||B==9||B==11){
            f=true;
        }
    }else{
        if(B==1||B==3||B==5||B==7||B==8||B==10||B==12)f=true;
    }
    f?cout<<"Yes":cout<<"No";

    return 0;

}


Measured memory_bytes: 256
#include<iostream>

using namespace std;

#define MAX 7

#define VMAX 1000



int m, n, counter;

int value[MAX+1], amount[MAX+1];



int compute(){

    int T[MAX+1][VMAX+1];

    for ( int i = 0; i <= m; i++ )

	for ( int j = 0; j <= n; j++ ) T[i][j] = 0;

    for ( int j = 0; j <= n; j++ ) T[0][j] = 0;

    for ( int i = 0; i <= m; i++ ) T[i][0] = 1;



    for ( int i = 1; i <= m; i++ ){

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

	for ( int j = 1; j <= n; j++ ){

	    for ( int a = 1; a <= amount[i]; a++ ){

		int k = j - a*value[i];

		if ( k >= 0 ) T[i][j] +=  T[i-1][k];

	    }

	}

    }



    int maxe = 0;

    for ( int i = 1; i <= m; i++ ) maxe = max(maxe, T[i][n]);

    return maxe;

}



int main(){

    while( cin >> m, m ){

	for ( int i = 0; i < m; i++ ){

	    cin >> value[i+1] >> amount[i+1];

	}

	int g; cin >> g;

	for ( int i = 0; i < g; i++ ){

	    cin >> n;

	    cout << compute() << endl;

	}

    }

    return 0;

}

Measured memory_bytes: 0
#include <iostream>
using namespace std;
struct Plan{
        int t,x,y;
};
int abs(int x){
        return x<0?(x*-1):x;
}
int main(){
        int N;
        cin >>N;
        Plan plan[100010];
        plan[0].x=plan[0].y=plan[0].t=0;
        for(int i=1 ; i<=N ; i++ )
                cin >>plan[i].t>> plan[i].x >> plan[i].y ;
        Plan now;
        for(int i=1 ; i<=N ; i++ ){
                now.x=plan[i-1].x;
                now.y=plan[i-1].y;
                now.t=plan[i].t-plan[i-1].t;
                int dist=abs(plan[i].x-now.x)+abs(plan[i].y-now.y);
                if(dist>now.t){
                        cout<<"No"<<endl;
                        return 0;
                }
                if(!(now.t%2==dist%2)){
                        cout<<"No"<<endl;
                        return 0;
                }
        }
        cout<<"Yes"<<endl;
        return 0;
}

Measured memory_bytes: 1408
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

ans = 10 ** 18
for bit in range(1 << N):
    #check k
    count = 0
    for i in range(N):
        if bit & 1 << i > 0:
            count += 1
    if count < K:
        continue

    cost = 0
    h = -1
    for i in range(N):
        if bit & 1 << i > 0:
            if A[i] <= h:
                cost += h - A[i] + 1
                h += 1
        h = max(h, A[i])
    ans = min(ans, cost)
print(ans)




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

int main() {
	int N;
	while( cin >> N, N ) {
		int W, H;
		cin >> W >> H;
		vector<vector<bool>>D( W, vector<bool>( H ) );
		for( size_t i = 0; i < N; i++ ) {
			int a, b;
			cin >> a >> b;
			a--; b--;
			D[a][b] = 1;
		}
		int S, T;
		cin >> S >> T;
		vector<vector<int>>M( 104, vector<int>( 104 ) );

		int ans = 0;
		for( size_t i = 0; i < W - S + 1; i++ ) {
			for( size_t j = 0; j < H - T + 1; j++ ) {
				for( size_t k = 0; k < S; k++ ) {
					for( size_t l = 0; l < T; l++ ) {
						M[i][j] += D[i + k][j + l];
					}
				}
				ans = max( M[i][j], ans );
			}
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 3220
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <set>

using namespace std;

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

const int N = 1000001;
bool isP[N], dp[N];
int main(){
	FOR(i, 2, N) isP[i] = 1;
	FOR(i, 2, N){
		if(isP[i]) for(int j = i*2; j < N; j += i) isP[j] = false;
	}
	int n, x;
	while(cin >> n >> x, n|x){
		memset(dp, 0, sizeof(dp));
		int ans = 0;
		dp[0] = 1;
		rep(i, n){
			int val;
			cin >> val;
			rep(j, x+1-val){
				if(dp[j]){
					dp[j+val] = 1;
					if(isP[j+val]) ans = max(ans, j+val);
				}
			}
		}
		if(ans) cout << ans << endl;
		else cout << "NA" << endl;
	}

	return 0;
}

Measured memory_bytes: 3120
#include <iostream>
#include <cmath>

using namespace std;

int main()
{
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  int result;
  result = min(min(B + C, B + D), min(A + C, A + D));
  cout << result << endl;
  return 0;
}

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

using namespace std;

int n, m;
string e[15];
string text;
bool dp[5005][1<<12];

int main(void)
{
	while(1){
		cin >> n >> m;
		if(n == 0 && m == 0) break;
		
		string s;
		for(int i = 0; i < n; i++) cin >> e[i];
		
		text = "";
		for(int i = 0; i < m; i++){
			cin >> s;
			//s.erase(s.end()-1);
			text += s;
		}
		
		for(int i = 0; i <= text.size(); i++){
			for(int j = 0; j < (1<<n); j++){
				dp[i][j] = false;
			}
			dp[i][0] = true;
		}
		for(int i = 0; i <= text.size(); i++){
			for(int j = 0; j < n; j++){
				if(text.size() - i < e[j].size()) continue;
				if(text.substr(i, e[j].size()) != e[j]) continue;
				
				for(int k = 0; k < (1<<n); k++){
					if(k & (1<<j)) continue;
					if(!dp[i][k]) continue;
					dp[i+e[j].size()][k | (1<<j)] = true;
				}
			}
		}
		
		int ans = 0;
		for(int i = 0; i <= text.size(); i++){
			if(dp[i][(1<<n)-1]) ans++;
		}
		cout << ans << endl;
	}
	
	return 0;
}

Measured memory_bytes: 23060
#include <bits/stdc++.h>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
using namespace std;
const int MOD = 1000000007;
const int INF = 1e9;
typedef long long ll;

int main(){
    int H,W,h,w;
    cin >> H >> W >> h >> w;

    cout << (H-h)*(W-w) << endl;
    
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String line = br.readLine();
        int num = Integer.parseInt(line);
        int[][][] numAry = new int[4][3][10];
        
        //????????????
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 10; k++) {
                    numAry[i][j][k] = 0;
                }
            }
        }
        
        //input?????£??\
        for (int i = 0; i < num; i ++) {
            String[] aryInput = br.readLine().split(" ");
            
            int a = Integer.parseInt(aryInput[0]);
            int b = Integer.parseInt(aryInput[1]);
            int c = Integer.parseInt(aryInput[2]);
            
            numAry[a - 1][b - 1][c - 1] += Integer.parseInt(aryInput[3]);
        }
        
        //??????
        for(int i = 0; i < 4; i++){
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 10; k++) {
                    System.out.print(" ");
                    System.out.print(numAry[i][j][k]);
                }
                System.out.println();
            }
            if(i != 3){
                System.out.println("####################");
            }
        }
    }
}

Measured memory_bytes: 24588
#include <cmath>
#include <iostream>
#include <iomanip>
#include <set>
#include <string>
#include <vector>
#define MAXN 2000

using namespace std;

int n;
int x[MAXN], y[MAXN], r[MAXN];

double calc_dist(int i, int j) {
    double dx = x[i] - x[j], dy = y[i] - y[j];
    return max(0.0, sqrt(dx * dx + dy * dy) - r[i] - r[j]);
}

double d[MAXN];
bool vis[MAXN];

int main() {
    cin >> x[0] >> y[0] >> x[1] >> y[1];
    cin >> n;
    for (int i = 2; i < n + 2; i++)
        cin >> x[i] >> y[i] >> r[i];

    for (int i = 1; i < n + 2; i++)
        d[i] = 1e11;
    set <pair <double, int>> s;
    s.insert({0, 0});
    while (!s.empty()) {
        auto it = s.begin();
        double cur = it->first;
        int u = it->second;
        if (u == 1)
            break;
        s.erase(it);
        if (vis[u])
            continue;
        vis[u] = true;
        for (int i = 0; i < n + 2; i++) {
            if (i == u)
                continue;
            double nxt = cur + calc_dist(i, u);
            if (nxt < d[i]) {
                d[i] = nxt;
                s.insert({nxt, i});
            }
        }
    }
    cout << fixed << setprecision(12) << d[1] << endl;
}


Measured memory_bytes: 16000
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<functional>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define MOD 1000000007
#define f(i,n) for(int i=0;i<int(n);i++)
#define N 2000






int main() {
	int a[N];
	f(i, N)a[i] = 0;
	int n, x, mi, ma;
	bool v = true;
	scanf("%d", &n);
	mi = n;
	ma = 0;
	f(i, n) {
		scanf("%d", &x);
		a[x]++;
		mi = min(mi, x);
		ma = max(ma, x);
	}
	if (ma % 2 == 0) {
		if (ma != (2 * mi))v = false;
		if (a[mi] != 1)v = false;
		for (int i = mi + 1; i <= ma; i++) {
			if (a[i] < 2)v = false;
		}
	}
	else {
		if (ma != (2 * mi - 1))v = false;
		if (a[mi] != 2)v = false;
		for (int i = mi + 1; i <= ma; i++) {
			if (a[i] < 2)v = false;
		}
	}
	if(v)printf("Possible\n");
	else printf("Impossible\n");
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < n; ++i)
ll dx[4] = { 0, 1, 0, -1 };
ll dy[4] = { 1, 0, -1, 0 };
const ll INF = 1 << LLONG_MAX;
const ll MOD = 1e9 + 7;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll N, K;
    cin >> N >> K;
    vector<ll> A(N);
    rep(i, N) { cin >> A[i]; }
    ll ans = 0;
    ll mul = K * (K - 1) / 2 % MOD;
    for (int i = 0; i < N; ++i) {
        ll right = 0, left = 0;

        for (int j = i + 1; j < N; ++j) {
            if (A[i] > A[j]) {
                right++; // A[i]より小さい右側の数
            }
        }
        ans = (ans + K * right) % MOD;

        for (int j = 0; j <= i - 1; ++j) {
            if (A[i] > A[j]) {
                left++; // A[i]より小さい数全ての個数
            }
        }
        ans = (ans + (right + left) * mul) % MOD;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<numeric>

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

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

const int mod = 1e9 + 7;
const long double pi = 3.141592653589793238462643383279502884197;
const long double eps = 1e-7;

ll N, X;
ll path = 0;
ll lside, sside;

ll solve(ll a, ll b) {
	if (b == 0) {
		return -a;
	}
	else {
		return 2 * (a / b) * b + solve(b, a % b);
	}
}

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

	if (X == 0) {
		cout << 0 << endl;
		return 0;
	}

	if (X < N - X) { X = N - X; }

	lside = X;
	sside = N - X;

	path += N;
	while (sside != 0) {
		path += 2 * (lside / sside) * sside;

		ll buf_sside = sside;
		sside = lside % sside;
		lside = buf_sside;
	}
	path -= lside;

	cout << path << endl;

	return 0;
}

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


int main(){
	char b;
	cin >> b;
	char ans;
	switch(b){
		case 'A':
			ans = 'T';
			break;
		case 'T':
			ans = 'A';
			break;
		case 'G':
			ans = 'C';
			break;
        case 'C':
			ans = 'G';
			break;
		default:
			break;

	}
	cout << ans << endl;

}

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

int qtmp(const void *a,const void *b){
    return *(int*)a - *(int*)b;
}

int main(void){
    int n,m;
    int i,j;

    while(1){
    scanf("%d %d",&n,&m);
    
    if(n==0 && m==0)break;

    int v[n];

    for(i=0;i<n;i++){
        scanf("%d",&v[i]);
    }

    qsort(v,n,sizeof(int),qtmp);

    int ans = -1;
    for(i=0;i<n-1;i++){
        for(j=i+1;j<n;j++){
            if(v[i] + v[j] > ans && v[i] + v[j] <= m){
                ans = v[i] + v[j];
            }
        }
    }

    if(ans == -1){
        printf("NONE\n");
    }
    else{
        printf("%d\n",ans);
    }
    
    }
    return 0;
}


Measured memory_bytes: 2032
import sys
sys.setrecursionlimit(10 ** 9)

def gcd(a, b):
    if a < b:
        a, b = b, a
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)

a, b, c, d = map(int, input().split())
divc = b // c - a // c
if a % c == 0:
    divc += 1
divd = b // d - a // d
if a % d == 0:
    divd += 1
    
lcm = c * d // gcd(c, d)
divlcm = b // lcm - a // lcm
if a % lcm == 0:
    divlcm += 1


div_or = divc + divd - divlcm
print(int(b - a + 1 - div_or))


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define mp make_pair
#define mt make_tuple
#define lb lower_bound
#define ub upper_bound
#define fr front
#define fi first
#define sc second
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

int main()
{
	int n, k;
	scanf("%d %d", &n, &k);
	
	int a[n], mx = 0;
	for(int i = 0; i < n; i++){
		scanf("%d", &a[i]);
		mx = max(mx, a[i]);
	}
	int l = 1, r = mx;
	int ans = mx;
	
	while(l <= r){
		int mid = (l + r) / 2;
		ll ct = 0;
		
		for(int i = 0; i < n; i++){
			ct += 1LL * (a[i] - 1) / mid;
		}
		if(ct <= k){
			ans = min(ans, mid);
			r = mid - 1;
		}
		else {
			l = mid + 1;
		}
	}
	printf("%d\n", ans);
}

Measured memory_bytes: 4400
n = int(raw_input())
R = []
R.append(int(raw_input()))
minv = R[0]
maxv = -1 * 10**9
for j in range(1,n):
    R.append(int(raw_input()))
    maxv = max(maxv,R[j]-minv)
    minv = min(minv,R[j])
print maxv

Measured memory_bytes: 16808
#include <iostream>
#include <string>
#include <vector>
using namespace std;

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

Measured memory_bytes: 1408
#include<iostream>
#include<cstdio>
#include<math.h>
#include<string>
#include<algorithm>
#include<functional>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define INF 999999
#define EPS 1.0e-6

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<P,int> PP;

int n, c;
vector<P> v[105000];
vector<P> vv;
priority_queue<int, vector<int>, greater<int>> q;

int main()
{

	cin >> n >> c;
	int si, ti, ci;
	for (int i = 0; i < n; i++) {
		cin >> si >> ti >> ci;
		ci--;
		v[ci].push_back(P(si, ti));
	}
	for (int i = 0; i < c; i++) {
		if (!v[i].empty()) {
			sort(v[i].begin(), v[i].end());
			int s = v[i][0].first, t = v[i][0].second;
			int ope = 0;
			for (int j = 1; j < v[i].size(); j++) {
				int curs = v[i][j].first;
				int curt = v[i][j].second;
				if (t == curs) {
					t = curt; ope = 0;
				}
				else {
					vv.push_back(P(s, t));
					s = curs; t = curt;
					ope = 1;
				}
			}
			if (ope == 0)vv.push_back(P(s, t));
		}
	}
	//cout << (int)vv.size() << endl;

	sort(vv.begin(), vv.end());
	q.push(vv[0].second);
	for (int i = 1; i < vv.size(); i++) {
		int si = vv[i].first;	
		int tc = q.top();
		if (si > tc) {
			q.pop();
			q.push(vv[i].second);
		}
		else {
			q.push(vv[i].second);
		}
	}
	cout << (int)q.size() << endl;


	return 0;
}

Measured memory_bytes: 4984
def __gcd__(m,n):
    x,y=max(m,n),min(m,n)
    if x%y==0:
        return y
    else:
        while x%y!=0:
            z=x%y
            x,y=y,z
        else:
            return z
        
from functools import reduce
def GCD(*X):
    return reduce(__gcd__,X)

N,M=map(int,input().split())

Q=M//N
R=M%N

for i in range(Q,0,-1):
    if M%i==0:
        print(i)
        break


Measured memory_bytes: 41596
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define FORR(i,a,b) for (int i=(a);i>=(b);i--)
#define pb push_back
#define pcnt __builtin_popcount
#define show(x) cout<<#x<<" = "<<x<<endl;
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define fi first
#define se second
#define rng(a) (a.begin()),(a.end())
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define sz(x) (int)(x).size()
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef set<int> si;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pll> vpll;
typedef set<ll> sl;
typedef __int128_t lll;
typedef pair<lll,lll> plll;
typedef vector<lll> vlll;
template<typename T>string join(vector<T>&v)
{stringstream s;FOR(i,0,sz(v))s<<' '<<v[i];return s.str().substr(1);}
ll gcd(ll a,ll b){if(a>b)swap(a,b);for(;a>0;b%=a,swap(a,b));return b;}
int modpow(ll a,ll n,int m){if(a==0)return a;ll p=1;for(;n>0;n/=2,a=a*a%m)if(n&1)p=p*a%m;return(int)p;}
void dout(double d){printf("%.12f\n",d);}

const int iinf = 1e9;
const ll linf = 1e18;
const int mod = 1e9+7;
const double pi = acos(-1);
const double eps = 1e-10;
int n, m;
bool G[8][8];
ll memo[256][8];

main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n >> m;
  FOR(i, 0, m){
    int a, b;
    cin >> a >> b;
    a--; b--;
    G[a][b] = true;
    G[b][a] = true;
  }
  memo[1][0] = 1;
  FOR(i, 2, 1<<n)FOR(j, 0, n) if((1<<j)&i)FOR(k, 0, n) if(G[j][k]) memo[i][j] += memo[i-(1<<j)][k];
  ll ans = 0;
  FOR(i, 0, n) ans += memo[(1<<n)-1][i];
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int, int>P;
typedef long long ll;

int main() {
	int a, p; cin >> a >> p;
	cout << (a * 3 + p) / 2 << endl;
	return 0;
}

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

using namespace std;

int main(){
    string s = "";
    cin >> s;
    if(s=="Sunny"){
        cout << "Cloudy";
    }
    else if(s=="Cloudy"){
        cout << "Rainy";
    }
    else{
        cout << "Sunny";
    }

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c;
	scanf("%d %d %d",&a,&b,&c);
	if(a<c&&c<b||a>c&&c>b)
		printf("Yes");
	else
		printf("No");
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
 
int main(){
    int k, x;
    cin >> k >> x;
    for(int i = ( x - (k - 1)); i <= (x + (k - 1)); i++){
        cout << i << " ";
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 3552
#include <algorithm>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <list>
#include <cstdio>
#define INF 1LL<<60
#define MOD 1000000007ll
#define EPS 1e-10
#define REP(i,m) for(long long i=0; i<m; i++)
#define FOR(i,n,m) for(long long i=n; i<m; i++)
#define pb push_back
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef long double ld;

ll pm(ll a, ll b){
  if(b == 1) return a;
  else if(b % 2 == 0){
    ll k = pm(a, b/2);
    return (k*k)%MOD;
  }
  else return (a * pm(a, b-1)) % MOD;
}

int main(){
  ll h, w, a, b;
  cin >> h >> w >> a >> b;
  ll c[w];
  c[0] = 1;
  FOR(i, 1, w){
    c[i] = (c[i-1] * (h-a-1+i)) % MOD;
    (c[i] *= pm(i, MOD-2)) %= MOD;
  }
  ll d[w-b];
  d[0] = 1;
  FOR(i, 1, w-b){
    d[i] = (d[i-1] * (a+i)) % MOD;
    (d[i] *= pm(i, MOD-2)) %= MOD;
  }
  ll e[w-b];
  e[0] = c[b];
  FOR(i, 1, w-b) e[i] = (c[i+b] - c[i-1+b] + MOD) % MOD;
  ll ans = 0;
  REP(i, w-b){
    ans += (e[i] * d[w-b-i-1]);
    ans %= MOD;
  }
  cout << ans << endl;
	return 0;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int main(){
    int x,y,n,b=0,o;
	cin>>n;
	for (o=0;o<n;o++){
		cin>>x;
		for(y=2;y*y<=x;y++){
			if(x%y==0){
				goto loop;
			}
		}
		b++;
		loop:;
	}
	cout<<b<<endl;
}



Measured memory_bytes: 3100
#include <iostream>
#include <iomanip>
#include <string>
#include <map>
#include <unordered_map>
#include <vector>
#include <cmath>
#include <algorithm>

typedef long long ll;
typedef long double ld;

using namespace std;
int main()
{
  int cnt = 0;
  string s, t;
  cin >> s >> t;
  for (int i = 0; i < 3; ++i) if (s[i] == t[i]) ++cnt;
  cout << cnt;
}


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

using namespace std;

int f(int x, int y) {
	return ceil((log(x) - log(y)) / log(4));
}

int a[222222];
long d[2][222222][16];
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		scanf("%d", a + i);
	for (int k = 0; k < 2; k++) {
		for (int i = n - 1; i--;) {
			for (int j = 0; j < 16; j++) {
				int r = max(0, f(a[i], a[i + 1]) + j);
				d[k][i][j] = r < 16 ? d[k][i + 1][r] + r : d[k][i + 1][15] + r + (n - i - 2)*(r - 15);
			}
		}
		if (!k) for (int i = 0; i < n / 2; i++)
			swap(a[i], a[n - i - 1]);
	}
	long m = 1e18;
	for (int i = 0; i < n; i++)
		m = min(m, (d[0][i][0] + d[1][n - i][0]) * 2 + i);
	cout << m << endl;
	return 0;
}


Measured memory_bytes: 54272