akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

const int INF = 1<<30;

typedef struct{
    int s, t, d;
}Edge;

int V, E, R;

bool bellman_ford(vector<Edge> &edges, int s, vector<int> &d){
    d[s] = 0;
    
    bool updated = true;
    for(int i=0; i<V; i++){
        updated = false;
        for(auto edge: edges){
            if(d[edge.s] != INF && d[edge.t] > d[edge.s] + edge.d){
               d[edge.t] = d[edge.s] + edge.d;
                updated = true;
            }
        }
    }
    return updated;
}

int main(){
    cin >> V >> E >> R;
    vector<Edge> edges;
    for(int i=0; i<E; i++){
        int s, t, d;
        cin >> s >> t >> d;
        edges.push_back({s, t, d});
    }
    
    vector<int> d(V, INF);
    bool neg_loop = bellman_ford(edges, R, d);
    
    if(neg_loop){
        cout << "NEGATIVE CYCLE" << endl;
    }else{
        for(auto v: d){
            if(v == INF)
                cout << "INF" << endl;
            else
                cout << v << endl;
        }
    }
    
    return 0;
}

Measured memory_bytes: 3176
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
using namespace std;
using Graph = vector<vector<int>>;
typedef long long ll;
const int mod= 1e+9+7;

int main(){
    char c; cin>>c;
    if(c=='a'||c=='i'||c=='u'||c=='e'||c=='o'){
        cout<<"vowel"<<endl;
    }
    else cout<<"consonant"<<endl;
}

















































Measured memory_bytes: 3564
#include <iostream>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <list>
#include <set>
#include <unordered_set>
#include <vector>
#include <utility>
#include <algorithm>
#include <queue>
#include <stack>
#include <cstdint>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>

#define rep(i, n) for(ll (i) = 0;(i) < (n);(i)++)
#define mp(a, b) make_pair((a),(b))
#define bs(n) ((ull)1<<(ull)n)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

constexpr ll inf = INT64_MAX / 4;
constexpr double pi = asin(1) * 2;
constexpr ll mod = 1000000007;
constexpr double eps = 0.000000001;

int main() {
    double l;
    cin >> l;
    double v = l / 3;
    cout << setprecision(20) << v * v * v << endl;
}

Measured memory_bytes: 256
package main

import "fmt"

func getMax(n, m int) (max int) {
	if n > m {
		max = n
	} else {
		max = m
	}
	return
}

func main() {
	var N int
	fmt.Scan(&N)
	A := make([][]int, 2)
	for i := 0; i < 2; i++ {
		A[i] = make([]int, N)
		for j := 0; j < N; j++ {
			fmt.Scan(&A[i][j])
		}
	}
	u, d := 0, 0
	for i := 0; i < N; i++ {
		d = getMax(d+A[1][i], u+A[0][i]+A[1][i])
		u += A[0][i]
	}
	fmt.Println(d)
}


Measured memory_bytes: 512
# -*- coding: utf-8 -*-

import sys

debug = False

def log(text):
    if debug:
        print(text)

def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
        lines.append(input())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]


    t = [int(c) for c in lines[0]]

    return (t, )


def solve(t, ):

    if debug:
        log("t=%s" % t)
    
    tmp = []
    for e in t:
        if e == 0:
            tmp.append(False)
        else:
            tmp.append(True)
    
    result = 0
    if len(t) == 1:
        pass
    else:
        for i in range(1, len(tmp)):
            if tmp[i-1] == tmp[i]:
                tmp[i] = not tmp[i-1]
                result = result + 1
        # while True:
        #     if debug:
        #         log("tmp=%s" % tmp)
        #     result_tmp = result
        #     for i in range(1, len(tmp)):
        #         if tmp[i-1] == tmp[i]:
        #             tmp[i] = not tmp[i-1]
        #             result = result + 1
        #             break
        #     if result_tmp == result:
        #         break
                

    return result


def main():
    # 出力

    print("%s" % solve(*parse_input()))

if __name__ == '__main__':

    main()


Measured memory_bytes: 4764
#include<iostream>
#include<set>
#include <bitset>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include <cstdio>
#include<algorithm>
#include <sstream>
#include<string.h>
#include <cmath>
#include <iomanip>
#include <string>
#include<list>
#include <limits>
#include <numeric>
#include <type_traits>
#define int long long
#define ll long long
#define mod  1000000007
#define MOD  1000000007
#define inf 1e17
#define rep(i,j,n) for(int i=j;i<n;i++)
#define P pair<int,int>
#define ps push_back
#define all(x) x.begin(),x.end()
double pi = 3.141592653589793;
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
//ここから始めよう
vector<int>v[114514];
vector<int>rev[114514];
int ok[114514];
int depth[114514];
bool used[114514];
void dfs(int k){
    used[k]=true;
    for(int e:v[k]){
        depth[e]=max(depth[e],depth[k]+1);
        ok[e]--;
        if(!used[e]&&!ok[e])dfs(e);
    }
}
signed main(){
    int n,m;cin>>n>>m;
    rep(i,0,n){
        ok[i]=0;
        depth[i]=-1;
        used[i]=false;
    }
    rep(i,0,n+m-1){
        int a,b;cin>>a>>b;
        a--;b--;
        ok[b]++;
        v[a].ps(b);
        rev[b].ps(a);
    }
    int k;
    rep(i,0,n){
        if(ok[i]==0){
            depth[i]=0;k=i;break;
        }
    }
    dfs(k);
    rep(i,0,n){
        if(rev[i].size()==0){
            cout<<0<<endl;continue;
        }
        for(int e:rev[i]){
            if(depth[i]==depth[e]+1){
                cout<<e+1<<endl;
                continue;
            }
        }
    }return 0;
}

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

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
#include <string>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <climits>
#include <bitset>
#include <array>
#include <deque>
#include <queue>
#include <map>
#define all(x) (x).begin(),(x).end()

void solve(){

}
int main(){
    int N,T;
    cin >> N >> T;
    vector<int> t(N);
    for (int i = 0; i < N; i++){
        cin >> t[i];
    }

    ll ans = T;
    for (int i = 1; i < N; i++){
        ans += min(t[i] - t[i-1], T);
    }

    cout << ans << endl;



    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 200005;
const int inf = 1e9 + 5;
int n, m;
vector<int> g[maxn];
int d[maxn];
int koji[maxn];
bool used[maxn];
void bfs(int s){
   used[s] = 1;
   for(int i=1;i<=n;i++)d[i] = inf;
   d[s] = 0;
   queue<int> q;
   q.push(s);
   while(!q.empty()){
      int v = q.front();
      q.pop();
      for(auto u : g[v]){
         if(!used[u]){
            used[u] = 1;
            d[u] = d[v] + 1;
            koji[u] = v;
            q.push(u);
         }
      }
   }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> m;
    for(int i=0;i<m;i++){
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    bfs(1);
    for(int i=1;i<=n;i++){
        if(d[i] == inf)return cout << "No", 0;
    }
    cout << "Yes" << endl;
    for(int i=2;i<=n;i++)cout << koji[i] << endl;
    return 0;
}


Measured memory_bytes: 13360
input_data = input()

if(input_data == "SUN"):
  print(7)
elif(input_data == "MON"):
  print(6)
elif(input_data == "TUE"):
  print(5)
elif(input_data == "WED"):
  print(4)
elif(input_data == "THU"):
  print(3)
elif(input_data == "FRI"):
  print(2)
elif(input_data == "SAT"):
  print(1)
else:
  pass

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

using namespace std;

int main()
{
	int n;
	cin >> n;
	char storeName[25 + 1];
	cin >> storeName;
	int storeNameLen = strlen(storeName);
	
	int canMake = 0;
	for (int i = 0; i < n; i++) {
		char board[100 + 1];
		cin >> board;
		int boardLen = strlen(board);

		vector<int>* charlist = new vector<int>[2];
		for (int j = 0; j < 2; j++) {
			for (int k = 0; board[k] != '\0'; k++) {
				if (board[k] == storeName[j]) 
					charlist[j].push_back(k);
			}
		}

		if (charlist[0].size() > 0 && charlist[1].size() > 0) {
			bool isExist = false;
			for (int j = 0; j < charlist[0].size(); j++) {
				for (int k = 0; k < charlist[1].size(); k++) {
					if (charlist[1][k] > charlist[0][j]) {
						int interval = charlist[1][k] - charlist[0][j];
						int pos = charlist[1][k];

						bool allSame = true;
						for (int l = 2; l < storeNameLen; l++) {
							pos += interval;
							if (pos > boardLen || board[pos] != storeName[l]) {
								allSame = false;
								break;
							}
						}
						if (allSame) {
							isExist = true;
							canMake++;
							break;
						}
					}
				}
				if (isExist) break;
			}
		}
	}

	cout << canMake << endl;

	return 0;
}

Measured memory_bytes: 1232
def greatest_common_devisor(x, y):
    if y == 0:
        return x
    x, y = y, x % y
    return greatest_common_devisor(x, y)
x, y = map(int, input().split(' '))
if x < y:
    tmp = x
    x = y
    y = tmp
print(greatest_common_devisor(x, y))


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

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

    int max_len = 0;
    for (int d = 1; d <= n - 1; d++) {
        int l = 0;
        for (int i = 0; i < n - d; i++) {
            if (s.at(i) == s.at(i + d)) l++;
            else l = 0;
            max_len = max(max_len, min(d, l));
        }
    }

    cout << max_len << endl;
}  

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

//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
#define PI 3.14159265359 //πの値
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素

uint64_t cbn(uint64_t n, uint64_t k) {
    uint64_t r = 1;
    for (uint64_t d = 1; d <= k; ++d) {
        r *= n--;
        r /= d;
    }
    return r;
}

int main(){
  ll N,K;
  cin >> N >> K;
  cout << cbn(N,2)+cbn(K,2);
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin>>s;
    int i,j;
    for(i = 0; i < s.size(); i++)
    {
        if(s[i] == 'A')
            break;
    }
    for(j = s.size() - 1; j >= 0; j--)
    {
        if(s[j] == 'Z')
            break;
    }
    cout<<(j - i + 1)<<endl;
    return 0;
}


Measured memory_bytes: 640
/*
	Created by : imay_10
	" It won't be EASY, but I'll make it "
*/

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

typedef long long int ll;
const int mod = 1e9+7;
const ll inf = 1e18;
const double pi = 3.1415926535897932384626;

// Utility for fast exponentiation
ll mpow(ll a,ll b,ll m){
    ll res=1;
    //a%=m;
    while(b){
    	if(b%2) res=res*a%m;
		a=a*a%m;
		b/=2;
	}
	return res;
}

// Utility for GCD Calculation
ll gcd(ll a,ll b){
	if(b==0) return a;
	return gcd(b,a%b);
}

void solve(){
	//code
	int n;
	cin>>n;
	
	if(n>=400 and n<=599) cout<<8;
	else if(n>=600 and n<800) cout<<7;
	else if(n>=800 and n<1000) cout<<6;
	else if(n>=1000 and n<1200) cout<<5;
	else if(n>=1200 and n<1400) cout<<4;
	else if(n>=1400 and n<1600) cout<<3;
	else if(n>=1600 and n<1800) cout<<2;
	else if(n>=1800 and n<2000) cout<<1;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	solve();
 	return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define MOD (1000000007)
#define vi vector<int>
#define vl vector<ll>
#define vb vector<bool>
#define vvi vector<vi>
#define vvl vector<vl>
#define pii pair<int, int>
#define pli pair<ll, int>a
#define pb push_back

#define mp make_pair
#define all(a) (a).begin(),(a).end()

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

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

ll keta(ll n){
  string s = to_string(n);
  ll num = s.size();
  return num;
}

const ll INF = 1LL << 60;

const int dh[4] = {1,0,-1,0};
const int dw[4] = {0,1,0,-1};

struct Edge{
  int to;
  int weight;
  Edge(int t, int w) : to(t), weight(w){}
};
using Graph = vector<vector<Edge>>;
using P = pair<ll, int>;

class UnionFind{
public:
  vi Parent;

  // 宣言と同時に Parent を初期化
  UnionFind(int n){
    Parent = vi(n,-1);
  }

  int root(int a){
    if(Parent[a] < 0) return a;
    return Parent[a] = root(Parent[a]);
  }

  int size(int a){
    return -Parent[root(a)];
  }

  bool issame(int a, int b){
    return root(a) == root(b);
  }

  bool merge(int a, int b){
    a = root(a);
    b = root(b);

    if(a == b) return false;

    if(size(a) < size(b)) swap(a,b);
    Parent[a] += Parent[b];
    Parent[b] = a;

    return true;
  }
};

int main(){
  ll x; cin >> x;
  ll ans = (x/11LL)*2LL;
  x %= 11LL;
  if(x > 0){
    x -= 6;
    ans++;
  }
  if(x > 0){
    x -= 5;
    ans++;
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int N,Q;
ll a[100000];
 
ll solve(ll S){
  ll sum=0,ans=0,k=0;
  for(int i=0;i<N;i++){
    sum+=a[i];
    while(sum>S){
      sum-=a[k];
      k++;
    }
    ans+=(i-k+1);
  }
  return ans;
}
 
int main(){
 
  scanf("%d %d",&N,&Q);
  for(int i=0;i<N;i++)scanf("%lld",&a[i]);
  for(int i=0;i<Q;i++){
    ll x;
    scanf("%lld",&x);
    printf("%lld\n",solve(x));    
  }
 
  return 0;
}

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

int main() {
    long long N;
    cin >> N;
    vector<string> s(N);
    rep(i, N) {
        cin >> s[i];
        sort(s[i].begin(), s[i].end());
    }
    sort(s.begin(), s.end());
    long long cnt = 1;
    long long ans = 0;
    s.push_back("");
    rep(i, N) {
        if (s[i] == s[i + 1]) {
            cnt += 1;
        } else {
            ans += cnt*(cnt - 1)/2;
            cnt = 1;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 8064
use std::io;


/// https://beta.atcoder.jp/contests/apc001/tasks/apc001_b
/// sum(b) - sum(a)
fn main() {
    let _n = read_one::<isize>();
    let a = read::<isize>();
    let b = read::<isize>();

    let sum_a = a.iter().sum::<isize>();
    let sum_b = b.iter().sum::<isize>();
    let time = a.iter().zip(b.iter())
        .map(|(x, y)| if x < y { (y - x + 1) / 2 } else { 0 })
        .sum::<isize>();

    if time <= sum_b - sum_a && sum_b >= sum_a {
        println!("Yes");
    } else {
        println!("No");
    }
}


#[allow(dead_code)]
fn read<T>() -> Vec<T>
where T:
    std::str::FromStr,
    T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.split_whitespace()
        .map(|s| s.trim().parse().unwrap())
        .collect()
}

#[allow(dead_code)]
fn read_one<T>() -> T
where T:
    std::str::FromStr,
    T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.trim().parse().unwrap()
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define int long long
#define N 100010
using namespace std;
const int INF = 1LL<<50;
const int mod = (1e9)+7;
const double EPS = 1e-8;
const double PI = 6.0 * asin(0.5);
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
typedef pair<int,int> P;
int n,K;
P A[N];
int compare(int a,int b){
  int i=0,j=0;
  while(a) i++,a/=2;
  while(b) j++,b/=2;
  return a < b;
}

int can(int a,int num){
  for(int i=0;i<=30;i++){
    int x = 1<<i;
    if(x < a) continue;
    if((K>>i & 1) && x != a) continue;
    if(num>>i & 1) return 0;
  }
  return 1;  
}

int solve(){
  sort(A,A+n); 
  vector<int> ok;
  for(int i=1;i<=K;i*=2) if( i&K ) ok.push_back(i);
  int res = 0;
  for(int i=0;i<n;i++) if((A[i].first & K) == A[i].first) res += A[i].second;

  for(int i=0;i<=30;i++){
    int a = 1<<i;
    if(a > K)continue;
    if((K >> i & 1) == 0 ) continue;
    int sum = 0;
    for(int i=0;i<n;i++){
      if(!can(a,A[i].first)) continue;
      sum += A[i].second;
    }
    Max(res,sum);
    //cout<<a<<" "<<res<<endl;
  }
  return res;
}

unordered_map<int,int> dp;
signed main(){
  
  cin>>n>>K;
  
  for(int i=0;i<n;i++){
    cin>>A[i].first >> A[i].second; 
    if(A[i].first > K) n--,i--;
  }
  cout<<solve()<<endl;
  return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int mod=1e9+7;
int main() {
string s;
cin>>s;
bool flag=false,check=true;
if(s.at(0)=='A'){
   for(int i=1;i<s.size();i++){
      if(1<i&&i<s.size()-1&&s.at(i)=='C'&&check){
         check=false;
         flag=true;
         continue;
      }
  if(s.at(i)-'Z'<=0){
         flag=false;
         break;
      }
   }
}
if(flag)cout<<"AC"<<endl;
else cout<<"WA"<<endl;
}


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;
 
const int mod = 1000000007;

int main() {
  int n;
  cin >> n;
  vector<ll> a(n);
  rep(i,n) cin >> a[i];
  ll ans = 0;
  rep(i, 60) {
    ll x = 0;
    rep(j,n) if (a[j]>>i&1) ++x;
    ll now = x*(n-x)%mod;
    rep(j,i) now = now*2%mod;
    ans += now;
    ans %= mod;
  }
  cout << ans << endl;
  return 0;
}

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

using ll = long long;

int main() {
    ll a, b; cin >> a >> b;
    ll g = __gcd(a, b);

    int ans = 1;
    for(ll x = 2; x * x <= g; ++x) {
        if(g % x == 0) {
            ans += 1;
            while(g % x == 0) g /= x;
        }
    }
    if(g > 1) ans += 1;

    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#define p pair <int,int>
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
using namespace std;
ll q,l[100005],r[100005],table[100005];

bool is_prime(int n)
{
  if(n<=1) return false; 
  for(int i = 2; i * i <= n; ++i){
    if(n%i ==0)
      {
	return false;
      }
  }
  return true;
}


int main(int argc,char const* argv[])
{
  cin >> q;
  rep(i,q)
    {
      cin >> l[i] >> r[i];
    }
  for(int i=1;i<=100000;i++)
    {
      if(is_prime(i) && is_prime((i+1)/2)) table[i]++;
    }
  for(int i=1;i<=100000;i++)
    {
      table[i]+=table[i-1];
    }
  rep(i,q)
    {
      cout << table[r[i]]-table[l[i]-1] << endl;
    }
  return 0;
}
  


Measured memory_bytes: 2944
#include<iostream>
#include<stdio.h>
using namespace std;
int main(){
	int a[3],i,j,n;
	for(i=0;i<3;i++){
		cin>>a[i];
	}
		for(i=0;i<2;i++){
			for(j=i+1;j<3;j++){
				if(a[i]>a[j]){
					n=a[i];
					a[i]=a[j];
					a[j]=n;
				}
			}
		}cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<endl;
    return 0;
}

Measured memory_bytes: 1164
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
using namespace std;
using ll = long long;
using P = pair<int, int>;
 
int main() {
  int n,l;
  cin >> n >> l;
  int sum = 0;
  for(int i = 1; i <= n; i++)sum += l + i -1;
  int sum2 = 0;
  int ans = 0;
  for(int i = 1; i <= n; i++){
    sum2 = sum - l - i + 1;
    if(abs(sum2 - sum) < abs(ans - sum)) ans = sum2;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
#define ALL(c) begin(c), end(c)
using namespace std;
using ll = long long;
using ld = long double;

const int N = 1e6+6;


int main(){
    //freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout);
    ios::sync_with_stdio(0);cin.tie(0);//cout.precision(12);cout<<fixed;
    
    ll n,a,b;
    cin>>n>>a>>b;
    
    ll ans = 0;
    if(a%2 == b%2){
        ans = (b-a)/2;
    }else{
        ll k = a-1;
        ll tb = b-k-1;
        ll res1 = (tb-1)/2 + k + 1;
        
        k = n-b;
        ll ta = a+k+1;
        ll resn = (n-ta)/2 + k + 1;
        
        ans = min(res1, resn);
    }
    
    cout<<ans<<endl;
    
    
    return 0;
}



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

template<typename First, typename Second, typename Third>
struct triple {
   First first;
   Second second;
   Third third;
};
#define  ll long long 
using namespace std;

void solve(){
   int x,y,z;
    cin>>x>>y>>z;
    string s=to_string(x);
    s+=to_string(y);
    s+=to_string(z);
    if(stoi(s)%4==0)
         cout<<"YES";
    else 
         cout<<"NO";
}
int main(){

  std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  solve();
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <ctime>
#include <cstring>
#include <cassert>
#include <bitset>
#include <sstream>
#include <queue>

#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define sz(a) ((int) (a).size())
#define eprintf(...) fprintf(stderr, __VA_ARGS__)

using namespace std;

typedef long long int64;
typedef long double ldb;

const long double eps = 1e-9;
const int inf = (1 << 30) - 1;
const long long inf64 = ((long long)1 << 62) - 1;
const long double pi = acos(-1);

template <class T> T sqr (T x) {return x * x;}
template <class T> T abs (T x) {return x < 0 ? -x : x;}

int main () {
    ios_base::sync_with_stdio(0);
//	freopen("input.txt", "rt", stdin);
//	freopen("output.txt", "wt", stdout);

	int n, m;
	cin >> n >> m;

	vector<vector<int>> adj(n);
	for (int i = 0; i < m; ++i) {
		int v1, v2;
		cin >> v1 >> v2;
		--v1, --v2;
		adj[v1].pb(v2);
		adj[v2].pb(v1);
	}

	vector<bool> used(n, false);
	vector<int> res;

	res.pb(0);
	used[0] = true;

	for (int t = 0; t < 2; ++t) {
		while(true) {
			int v = -1;
			for (int i = 0; i < sz(adj[res.back()]); ++i) {
				if (!used[adj[res.back()][i]]) {
					v = adj[res.back()][i];
					break;
				}
			}

			if (v == -1) {
				break;
			}
		
			res.pb(v);
			used[v] = true;
		}
		
		reverse(res.begin(), res.end());
	}

	cout << sz(res) << "\n";
	for (int i = 0; i < sz(res); ++i) {
		cout << res[i] + 1 << (i + 1 < sz(res) ? ' ' : '\n');
	}

	return 0;
}


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

using namespace std;

int main() {
	long long a, b, c;
cin >>  a >> b >> c;
	if(a%2 == 0 || b%2 == 0 || c%2 == 0) cout << 0 << endl;
	else {
		cout << min( min (a*b, b*c), a*c) << endl;
	}
	return 0;
}

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

int main() {
	int a, b, c;
	int count = 0;

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

	for (int i = a; i <= b; i++) {
		if (c % i == 0) {
			count++;
		}
	}
	printf("%d", count);

	cout << endl;
	return 0;
}

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

template<class T> void vin(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
}

struct Edge {
    int s, t, w;
};

int main() {
    int L;
    cin >> L;
    int r = log2(L);
    r = min(r, 19);
    int n = r + 1;
    vector<Edge> g;

    rep(i, r) {
        Edge e1, e2;
        e1.w = 0;
        e1.s = i+1;
        e1.t = i+2;
        e2.w = pow(2, i);
        e2.s = i+1;
        e2.t = i+2;
        g.push_back(e1);
        g.push_back(e2);
    }
    bool update = true;
    for (int t=n-1; t>=1; --t) {
        if (L - pow(2, t-1) >= pow(2, r)) {
            Edge e;
            e.w = L - pow(2, t-1);
            e.s = t;
            e.t = n;
            g.push_back(e);
            L -= pow(2, t-1);
        }
    }
    cout << n << ' ' << g.size() << endl;
    for (auto v : g) {
        cout << v.s << ' ' << v.t << ' ' << v.w << endl;
    }
}


Measured memory_bytes: 256
/*
[abc166] B - Trick or Treat
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
#define ALL(c) (c).begin(), (c).end()

const int MAX_N = 100;
const int MAX_K = 100;

int N, K;
int cnt[MAX_N];

ll solve() {
    int ans = 0;
    for (int i = 0; i < N; i++) {
        if (cnt[i] == 0) ans++;
    }

    return ans;
}

int main() {
    cin >> N >> K;
    for (int i = 0; i < K; i++) {
        int d;
        cin >> d;
        for (int j = 0; j < d; j++) {
            int a;
            cin >> a;
            a--;
            cnt[a]++;
        }
    }

    cout << solve() << endl;

    return 0;
}


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

#define rng(i, a, b) for (int i = int(a); i < int(b); i++)
#define rep(i, b) rng(i, 0, b)
#define gnr(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define per(i, b) gnr(i, 0, b)

using namespace std;

using ll = long long;
using P = pair<int, int>;

int main() {
  string s, t;
  cin >> s >> t;
  vector<int> sToT(26, -1);
  vector<int> tToS(26, -1);
  bool ok = true;
  for (int i = 0; i < s.size(); i++) {
    int sc = s.at(i) - 'a';
    int tc = t.at(i) - 'a';
    if ((sToT.at(sc) != -1 && sToT.at(sc) != tc)
        || (tToS.at(tc) != -1 && tToS.at(tc) != sc)) {
      ok = false;
      break;
    }
    sToT[sc] = tc;
    tToS[tc] = sc;
  }
  cout << (ok ? "Yes" : "No") << endl;
  return 0;
}


Measured memory_bytes: 776
#include<stdio.h>
#include<ctype.h>

int main(){
  
  int q, maxl, xi, yi, i, j, ii;
  char  X[1002], Y[1002];
  long int C[1001][1001], Z[150];
  
  scanf("%d", &q);
  
  for( ii = 0; ii < q; ii++){
    scanf("%s", X);
    scanf("%s", Y);
    /*????????°*/
    xi = 1;
    while(X[xi]){
      xi++;
    }
    yi = 1;
    while(Y[yi]){
      yi++;
    }
    
    C[0][0] = 0;
    for(i = 1; i <= xi; i++) {
    C[i][0] = 0;
    X[xi - i + 1] = X[xi - i];
    }
    for(i = 1; i <= yi; i++) {
    C[0][i] = 0;
    Y[yi - i + 1] = Y[yi - i];
    }
    X[0] = ' ';
    Y[0] = ' ';

    /* c[][]*/
    maxl = 0;
    for( i = 1; i <= xi; i++){
      for( j = 1; j <= yi; j++){
        if ( X[i] == Y[j] ){
          C[i][j] = C[i - 1][j - 1] + 1;
        } else {
          if( C[i - 1][j] > C[i][j - 1]){
            C[i][j] = C[i - 1][j];
          } else {
            C[i][j] = C[i][j - 1];
          }
        }
        
        if( maxl < C[i][j]){
          maxl = C[i][j];
        }
      }
    }
    
    Z[ii] = maxl;
  }
  
  for(ii = 0; ii < q; ii++){
    printf("%d\n",Z[ii]);
  }
  
  return 0;
}

Measured memory_bytes: 8428
import math


def resolve():
    import sys
    import string
    input = sys.stdin.readline
    # row = [int(x) for x in input().rstrip().split(" ")]
    # n = int(input().rstrip())
    a = int(input().rstrip())
    b = int(input().rstrip())
    c = int(input().rstrip())
    d = int(input().rstrip())
    e = int(input().rstrip())

    max_loss = 0
    ans = 0
    for x in [a,b,c,d,e]:
        if max_loss < (10 - (x % 10)) % 10:
            max_loss = 10 - (x % 10)
        ans += math.ceil(x / 10.0) * 10

    ans -= max_loss
    print(ans)

if __name__ == "__main__":
    resolve()


Measured memory_bytes: 71540
N = int(input())
S = input()
def RLE(S): # 文字列のランレングス圧縮(RunLengthEncoding)
    res = []
    if len(S)==0:
        return res
    now = S[0]
    id = 1
    num = 1
    while id < len(S):
        if now==S[id]:
            num+=1
            id+=1
        else:
            res+=(now,num),
            now=S[id]
            num=1
            id+=1
    res+=(now,num),
    return res # list[tuple(str,int),...]
print(len(RLE(S)))

Measured memory_bytes: 52444
#include <bits/stdc++.h>
using namespace std;
string s;
int n;
long long ans;
long long top[5];
void recursive_comb(int *indexes, int s, int rest, std::function<void(int *)> f) {
    if (rest == 0) {
        f(indexes);
    } else {
        if (s < 0) return;
        recursive_comb(indexes, s - 1, rest, f);
        indexes[rest - 1] = s;
        recursive_comb(indexes, s - 1, rest - 1, f);
    }
}
void foreach_comb(int n, int k, std::function<void(int *)> f) {
    int indexes[k];
    recursive_comb(indexes, n - 1, k, f);
}
int main() {
    cin>>n;
    for(int i=0;i<n;i++){
        cin >> s;
        if(s[0]=='M')top[0]++;
        if(s[0]=='A')top[1]++;
        if(s[0]=='R')top[2]++;
        if(s[0]=='C')top[3]++;
        if(s[0]=='H')top[4]++;
    }
    foreach_comb(5, 3, [](int *indexes) {
        ans+=top[indexes[0]]*top[indexes[1]]*top[indexes[2]];
    });
    cout<<ans<<endl;
};


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

int LCSLength(char *,char *,int,int);

int main(){
  char X[1001];
  char Y[1001];
  int n;
  int i;
  int x;
  int Xlength;
  int Ylength;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%s",X);
    scanf("%s",Y);
    Xlength=strlen(X);
    Ylength=strlen(Y);
    x=LCSLength(X,Y,Xlength,Ylength);
    printf("%d\n",x);
  }
  return 0;
}
int LCSLength(char *X,char *Y,int m,int n){
  int i,j;
  int c[m+1][n+1];
  for(i=0;i<=m;i++) c[i][0]=0;
  for(j=0;j<=n;j++) c[0][j]=0;
  for(i=1;i<=m;i++){
    for(j=1;j<=n;j++){
      if(X[i-1]==Y[j-1]) c[i][j]=c[i-1][j-1]+1;
      else if(c[i-1][j] >= c[i][j-1]) c[i][j] = c[i-1][j];
      else c[i][j] = c[i][j-1];
    }
  }
  return c[m][n];
}




Measured memory_bytes: 5628
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#define debug(x)  cerr << #x << " = " << x << endl
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;

const int maxN = 1e5 + 5;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;

ll gcd(ll a, ll b){return !b ? a : gcd(b, a % b);}
ll modP(ll a, ll b) {return (!b ? 1 : (modP(a, b / 2) * modP(a, b / 2) * (b % 2 ? a : 1)) % MOD);}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, cnt = 0;
	string s;
	cin >> s;
	n = s.size();
	for (int i = 0; i < n; i++){
		cnt += (s[i] - '0' == i % 2);
	}
	cout << min(cnt, n - cnt) << endl;
	return 0;
}



Measured memory_bytes: 512
#include "bits/stdc++.h"

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;

using namespace std;
using ll = long long;

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

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

  int H=in(),W=in();
  int h=in(),w=in();
  
  cout << H*W-h*W-w*H+h*w<< endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)


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

  ll n,m,v,p;
  cin >> n >> m >> v >> p;
  vector<ll> a(n);
  rep(i,n) cin >> a[i];
  sort(a.rbegin(),a.rend());
  ll midl=n-1;
  ll lb,ub;
  lb=ub=-10;
  ll bord=a[p-1];
  if(a[midl]==bord) lb=midl;
  else if(m+a[midl] < bord){
    ub=midl;
  }
  else{
    ll rest=v-p;
    if(rest<=0){
      lb=midl;
    }
    else {
      ll restp=rest*m;
      for(int j=n-1;j>=p-1;j--){
        if(j==midl) continue;
        if(j>midl) restp-=m;
        else{
          restp-= (a[midl]+m-a[j]);
        }
      }
      if(restp>0) ub=midl;
      else lb=midl;
    }
  }
  if(lb==n-1){
    cout << n << endl;
    return 0;
  }
  lb=p-1;
  ub=n-1;  
  while(ub-lb>1){
    ll mid=(ub+lb)/2;
    if(a[mid]==bord) lb=mid;
    else if(m+a[mid] < bord){
      ub=mid;
    }
    else{
      ll rest=v-p;
      if(rest<=0){
	lb=mid;
      }
      else {
	ll restp=rest*m;
	for(int j=n-1;j>=p-1;j--){
	  if(j==mid) continue;
	  if(j>mid) restp-=m;
	  else{
	    restp-= (a[mid]+m-a[j]);
	  }
	}
	if(restp>0) ub=mid;
	else lb=mid;
      }
    }
  }
  cout << lb+1 << endl;
  /*
  ll bord=a[p-1];
  ll ans=p;
  vector<ll> sum(n+1,0);
  rep1(i,n){
    sum[i] = sum[i-1]+a[i-1];
  }
  for(int i=p; i<n; i++){
    if(a[i] == a[p-1]){
      ans++;
    }
    else if(m+a[i] < bord){
      break;
    }
    else {
      ll rest=v-p;
      if(rest<=0) ans++;
      else{
	long double ten = ceil( ((long double )rest*m+sum[i+1]-sum[p-2+1]-a[i])/((long double)(n-p)));
	cout << "i ten " << i << " " << ten << endl;
	if(ten<=m+a[i]) ans++;
	else break;
      }
    }
    }*/
  return 0;
    

}


Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <cstring>
#include <functional>
#include <cmath>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define rep1(i,n) for(int i=1;i<=(n);++i)
#define all(c) (c).begin(),(c).end()
#define fs first
#define sc second
#define pb push_back
#define show(x) cout << #x << " " << x << endl
typedef long long ll;
ll p[64];
ll num(ll x,int j){
	return x/p[j+1]*p[j]+max(0LL,x%p[j+1]-p[j]);
}
void solve(int n){
	int nc=n;
	ll k[64],kc[64];
	rep(i,64) k[i]=-1;
	rep(i,n) cin>>k[i];
	rep(i,n) kc[i]=k[i];
//	while(n>0&&k[n-1]==0) n--;
//	if(n==-1){}
	rep(i,n){
		if(k[i]>=p[60]){
			puts("None");
			return;
		}
	}
	ll ansa=-1,ansb=-1;
	for(ll mo=kc[0]*2-1;mo<=kc[0]*2+1;mo++){
		ll a=0,b=0;
		ll m=mo;
		n=nc;
		rep(i,n) k[i]=kc[i];
		for(int i=n-1;i>=0;i--){
			if(k[i]==0) continue;
			if(k[i]==m){
				k[i]=0;
				a+=p[i],b+=p[i];
				continue;
			}
			if(k[i]>m){
				break;
			}
			rep(j,i) k[j]-=num(k[i],j);
			m-=k[i];
			b+=p[i]+k[i]-1;
			a+=p[i]-m;
			k[i]=0;
//			rep(j,n) show(k[j]);
//			show(m);
			rep(j,i) k[j]-=(m-num(m,j));
//			rep(j,n) show(k[j]);
			break;
		}
		bool can=true;
		rep(i,nc) if(k[i]!=0) can=false;
		if(1>a||a>b||b>1e18) can=false;
		if(can){
			if(ansa==-1){
				ansa=a,ansb=b;
			}else{
				puts("Many");
				return;
			}
		}
	}
	if(ansa==-1){
		puts("None");
		return;
	}
	cout<<ansa<<" "<<ansb<<endl;
}
int main(){
	p[0]=1;
	rep(i,63) p[i+1]=p[i]*2;
	while(true){
		int n;
		cin>>n;
		if(n==0) break;
		solve(n);
	}
}

Measured memory_bytes: 1164
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#define ll long long
#define F(i,a,b) for(int i=(a);i<=(b);i++)
#define mst(a,b) memset((a),(b),sizeof(a))
#define PII pair<int,int>
using namespace std;
template<class T>inline void read(T &x) {
    x=0; int ch=getchar(),f=0;
    while(ch<'0'||ch>'9'){if (ch=='-') f=1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    if(f)x=-x;
}
const int inf=0x3f3f3f3f;
const int p=1e9+7;
ll x,y;
ll calc(ll n)
{
	ll res=1;
	for(ll i=1;i<=n;i++) res=res*i%p;
	return res%p;
}
ll ksm(ll a,ll b)
{
	ll res=1%p;
	while(b)
	{
		if(b&1) res=res*a%p;
		a=a*a%p;
		b>>=1;
	}
	return res;
}
int main()
{
	cin>>x>>y;
	if(2*x-y<0||(2*x-y)%3!=0) puts("0");
	else if(2*y-x<0||(2*y-x)%3!=0) puts("0");
	else
	{
		ll a=(2*y-x)/3;
		ll b=(2*x-y)/3;
		ll temp=(x+y)/3;
		temp=calc(temp);
		a=calc(a),b=calc(b);
		ll ans=temp%p*ksm(a,p-2)%p*ksm(b,p-2)%p;
		cout<<ans%p<<endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ff { ios_base::sync_with_stdio(false);cin.tie(NULL);}
using namespace std;

typedef long long ll;
 ll  pp=1e9+7; 
double pi=3.141592653589793238;
  
 int main() {
        ff;
        ll n,d;
        cin>>n>>d;
        ll pk=d*d;
        ll x,y;
        ll cnt=0;
        while(n--){
            cin>>x>>y;
            if(pk>=(x*x+y*y)){
                cnt++;
            }
        }
        cout<<cnt<<endl;
		
    return 0;
}

            
		
        
           
  

Measured memory_bytes: 3652
# coding: utf-8
from math import ceil
N, H = map(int, input().split())
li = []
atop = 0
for _ in range(N):
    a, b = map(int, input().split())
    atop = max(atop, a)
    li.append(b)
li.sort(reverse=True)
# print(li)
ans = ceil(H/atop)
cnt = 0
for i in range(N):
    H -= li[i]
    cnt += 1
    ans = min(ans, cnt + max(0, ceil(H/atop)))
print(ans)

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

const int maxn=200006;
int l[maxn], r[maxn];
int num[maxn];

int main()
{
    ios::sync_with_stdio(0);
    int n;
    while(cin>>n){
        memset(l, 0, sizeof(l));
        memset(r, 0, sizeof(r));
        for(int i=0;i<n;i++){
            cin>>num[i];
            if(i>0){
                l[i] = max(num[i-1], l[i-1]);
            }
        }
        for(int i=n-2;i>=0;i--){
            r[i] = max(r[i+1], num[i+1]);
        }
        for(int i=0;i<n;i++){
            if(i==0){
                cout<<r[i]<<endl;
            }
            else if(i==n-1){
                cout<<l[i]<<endl;
            }
            else{
                cout<<max(l[i], r[i])<<endl;
            }
        }
    }
    return 0;
}


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

using namespace std;


#define MAXN 200001
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, a[MAXN], b[MAXN];
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    a[i]--;
    b[a[i]] = i;
  }
  int cur = 0, ans = 0;
  for (int i = 1; i < n; ++i) {
    if (b[i]>b[i-1]) {
      cur++;
    } else {
      ans = max(ans, cur);
      cur = 0;
    }
  }
  ans = max(ans, cur);
  cout << n-ans-1 << endl;
  return 0;
}


Measured memory_bytes: 1792
def result(letters, number, cant_zero):
    if letters <= 1:
        if number == 0:
            return 10 ** letters
        return 0
    diff = (10 - number%10) % 10
    variants = number % 10 - cant_zero
    if number % 10 == 0:
        variants = 10 - cant_zero
    number -= diff * (10**(letters-1) - 1)
    number = abs(number // 10)
    return variants * result(letters-2, number, 0)

d = int(input())
ans = 0
for i in range(20):
    ans += result(i, d, 1)
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define read ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#define endl '\n'
#define debug(x) cout<<#x<<": "<<x<<endl;
#define debug2(x, y) cout<<#x<<": "<<x<<"  |  "<<#y<<": "<<y<<endl;
#define forr(i, s, n) for(ll i=(s); i<(int)(n); ++i)
#define fori(i, n) forr(i, 0, n)
#define pb(n) push_back(n)
#define fst first
#define snd second
#define INF 2e9 + 5
#define LINF 1e18l + 5l
#define MOD 1000000007
#define EPS 1e-7
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef vector<ll> vll;
typedef vector<string> vs;

int main(){
    read;
    string a,b;
    cin>>a>>b;
    int dp[a.size() + 1][b.size() + 1];
    memset(dp, 0, sizeof dp);
    forr(i, 1, a.size() + 1) {
        forr(k, 1, b.size() + 1) {
            if(a[i - 1] == b[k - 1]) {
                dp[i][k] = max(dp[i - 1][k - 1] + 1, dp[i - 1][k]);
            } else {
                dp[i][k] = max(dp[i - 1][k], dp[i][k - 1]);
            }
        }
    }
    /*fori(i, a.size() + 1) {
        if(i == 0) cout<<"- ";
        else cout<<a[i - 1]<<" ";
        fori(k, b.size() + 1) {
            cout<<dp[i][k]<<" ";
        } cout<<endl;
    }*/
    string ans = "";
    int i = a.size(), k = b.size();
    int ant = dp[i][k];
    while(dp[i][k] > 0) {
        // debug(dp[i][k]);
        // debug2(dp[i - 1][k], dp[i][k - 1]);
        if(dp[i - 1][k] == ant) {
            i--;
        } else {
            if(dp[i][k - 1] == ant) {
                k--;
            } else {
                // debug2(i-1, k-1);
                ans += a[i - 1];
                k--;
                i--;
                ant = dp[i][k];
            }
        }
    }
    reverse(ans.begin(), ans.end());
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 35456
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define BIG 1000000010
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
typedef long long int ll;


int main(){
int a,b,c,d;
  cin>>a>>b>>c>>d;
  cout<<max(a*b,c*d)<<endl;

  return 0;
}







Measured memory_bytes: 256
#define rep(i, n) for (int i = 0; i < (n); i++)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int MOD = 1000000007;
// MAX int 2,147,483,647
// MAX O(n) 10^18

int main() {
    ll N, A, B;
    cin >> N >> A >> B;

    ll devided = N / (A + B);
    ll left = N % (A + B);

    ll ans = 0;
    ans += devided * A;
    ans += min(A, left);

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3652
// input! macro is published in the following URLs.
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
// https://github.com/tanakh/competitive-rs.git
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        s: chars,
        k: u64,
    }
    let mut count = 0u64;
    for c in s {
        if count == k - 1 {
            println!("{}", c);
            return;
        }
        match c {
            '1' => count += 1,
            _ => {
                println!("{}", c);
                return;
            }
        }
    }
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
int main(){
    
  int N;
  cin >> N;
  
  int times = 0;
  int chall = 0;
  
  int A;
  for (int i=0; i < N; i++){
      cin >> A;
      while (true){
          if (A % 2 != 0){
              break;
          }
          else {
              A /= 2;
              chall++;
          }
      }
    
    if (times > chall){
        times = chall;
    }
    else if (i == 0){
        times = chall;
    }
    
    chall = 0;
      
  }
  cout << times << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
int64_t MOD=1000000007;

int main() {
  int64_t N,K;
  cin>>N>>K;
  if(K%2==1){
    N/=K;
    int64_t ans=N*N*N;
    cout<<ans<<endl;
  }
  else{
    K/=2;
    int64_t A=0,B=0,i=1;
    while(N>=K){
      N-=K;
      if(i%2==0) A++;
      else B++;
      i++;
    }
    int64_t ans=A*A*A+B*B*B;
    cout<<ans<<endl;
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
#define ul unsigned long long int
#define va vector<long long int> a 
#define vb vector<long long int> b
#define M 1000000007
using namespace std;
ll t;
void fast(){cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);}
ll power(ll x,ul y,ll p){ll res = 1;x = x % p;if(x == 0)return 0;while (y > 0){if (y & 1)res = (res*x) % p;y = y>>1;x = (x*x) % p;}return res;}
void solve(){
	ll n,k;
	cin>>n>>k;
	ll a[n+1]={0};
	for(ll i=0;i<k;i++){
		ll m;
		cin>>m;
		ll b;
		for(ll j=0;j<m;j++){ cin>>b; a[b]++;}
	}
	ll count=0;
	for(ll i=1;i<=n;i++){
		if(a[i]==0) count++;
	}
	cout<<count<<"\n";
}
int main(){
	fast();
	solve();
	return 0;
}



Measured memory_bytes: 3696
k = int(input())
s = [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]
print(s[k-1])

Measured memory_bytes: 3060
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iterator>
#include <bitset>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <iomanip>
//#include <utility>
//#include <memory>
//#include <functional>
//#include <deque>
//#include <cctype>
//#include <ctime>
//#include <numeric>
//#include <list>
//#include <iomanip>

//#if __cplusplus >= 201103L
//#include <array>
//#include <tuple>
//#include <initializer_list>
//#include <forward_list>
//
//#define cauto const auto&
//#else

//#endif

using namespace std;


typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
    stringstream ss;
    ss << f;
    ss >> t;
}

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define reep(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) reep((i),0,(n))
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define F first
#define S second
#define mkp make_pair
#define RALL(v) (v).rbegin(),(v).rend()
#define DEBUG
#ifdef DEBUG
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#else
#define dump(x) 
#define debug(x) 
#endif
#define LDcout(x,n) fixed<<setprecision(n)<<x

#define MOD 1000000007LL
#define EPS 1e-8
static const int INF=INT_MAX/2;

void mainmain(){
	int n,m;
	while(cin>>n>>m,n){
		vvint wf1;
		vvint wf2;
		initvv(wf1,n,n,0);
		initvv(wf2,n,n,INF);
		rep(i,n) wf1[i][i]=wf2[i][i]=0;
		rep(i,m){
			int a,b,c;
			cin>>a>>b>>c;
			a--; b--;
			wf1[a][b]=wf1[b][a]=1;
			wf2[a][b]=wf2[b][a]=c;
		}
		rep(k,n) rep(i,n) rep(j,n){
			wf2[i][j]=min(wf2[i][j],wf2[i][k]+wf2[k][j]);
		}
		int ans=wf2[0][n-1];
		rep(i,n){
			rep(j,n){
				rep(k,n){
					if(wf1[i][k]&&wf1[k][j]){
						ans=min(ans,wf2[0][i]+wf2[j][n-1]);
					}
				}
			}
		}
		cout<<ans<<endl;
	}
}


signed main() {
	ios_base::sync_with_stdio(false);
  	cout<<fixed<<setprecision(0);
    mainmain();
}

Measured memory_bytes: 1308