akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define Elhabashy ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
void input()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
}
const int N=1e5+10,mod=1e9+7,OO=0x3f3f3f3f;
typedef long long ll;
ll n,x,y,dp[N][2];
vector<int>adj[N];
void dfs(int u=1,int p=-1){
    dp[u][0]=dp[u][1]=1;
    for(auto v:adj[u]){
        if(v==p)continue;
        dfs(v,u);
        dp[u][0]=(dp[u][0]*(dp[v][1]+dp[v][0]))%mod;
        dp[u][1]=(dp[u][1]*dp[v][0])%mod;
    }


}
int main()
{
    Elhabashy
    input();
    cin>>n;
    for(int i=1;i<n;i++){
        cin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dfs();
    cout<<(dp[1][0]+dp[1][1])%mod<<endl;
}


Measured memory_bytes: 17528
#include <iostream>
#include<cstdio>
using namespace std;
int main()
{
	int a;
	scanf("%d",&a);
	int s=1,f=0;
	if(a%2==0||a%5==0) printf("-1");
	else
	{ 
	while(1)
	{
		f=f*10+7;
		f=f%a;
		if(f%a==0) break;
		else s++;
	}
	printf("%d",s);
	}
	return 0;	
} 
 


Measured memory_bytes: 3236
#include<iostream>

using namespace std;

int main()
{
    int a[101][101],b[101][101];
    long long c[101][101];

    int n,m,l;

    cin>>n>>m>>l;

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

    for(int i=0;i<m;i++)
    {
        for(int j=0;j<l;j++)
        {
            cin>>b[i][j];
        }
    }

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<l;j++)
        {
            c[i][j]=0;
            for(int k=0;k<m;k++)
            {
                c[i][j]+=a[i][k]*b[k][j];
            }
            if(j)
            {
                cout<<" ";
            }
            cout<<c[i][j];
        }
        cout<<endl;
    }


    return 0;
}



Measured memory_bytes: 3152
use proconio::input;

fn main() {
    input! {
        n: usize,
        d: f64,
        p: [(f64, f64); n],
    }
    println!(
        "{}",
        p.iter()
            .map(|(x, y)| (x * x + y * y).sqrt())
            .filter(|&dist| dist <= d)
            .count()
    );
}


Measured memory_bytes: 7784
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T,class U> using P = pair<T,U>;
template<class T> using vec = vector<T>;
template<class T> using vvec = vector<vec<T>>;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)

struct tmp {
    string key;
    int value;
};

int main(){
    int n;
    cin >> n;
    map<string, int> mp;
    rep(i, n) {
        string s;
        cin >> s;
        mp[s]++;
    }
    int max_val = 0;
    vec<string> ans;
    for( auto i = mp.begin(); i != mp.end() ; ++i ) {
        if ( i->second > max_val) {
        max_val = i->second;
        ans = {};
        ans.push_back(i->first);
    } else if (i->second == max_val) {
        ans.push_back(i->first);
    }
        
    }
    sort(ans.begin(), ans.end());
    rep(i, ans.size()) cout << ans[i] << endl;


}

Measured memory_bytes: 26868
#include<stdio.h>
#include<string.h>
#define MAX 100010
int ans[MAX]={};

int main(){
  char str[MAX];
  scanf(" %s",str);
  int i;
  char temp='R';
  int count=0,j=0,len=strlen(str);
  for(i=0;i<len;i++) {
    if (temp==str[i]) {
      count++;
      continue;
    }
    if(temp=='R'){
      j=i;
      ans[j]+=count/2;
      ans[j-1]+=(count+1)/2;
    }else{
      ans[j-1]+=count/2;
      ans[j]+=(count+1)/2;
    }
    count=1;
    temp=str[i];
  }
  
  ans[j-1]+=count/2;
  ans[j]+=(count+1)/2;
  for(i=0;i<strlen(str);i++)
    printf("%d ",ans[i]);
  return 0;
}


/// confirm df==0 ///


Measured memory_bytes: 896
// https://beta.atcoder.jp/contests/abc069
// status:
// tag:

#define SUBMIT
//#define DEBUG

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

int H, W, N;
int grid[100][100];

int main() {
#ifdef SUBMIT
    auto& stream = cin;
#else
    stringstream stream(R"(2 2
3
2 1 1
)");
#endif
    stream >> H >> W;
    stream >> N;
    vector<int> a(N + 1);
    for (int i = 1; i <= N; ++i) stream >> a[i];

    int y = 0, x = 0;
    for (int i = 1; i <= N; ++i) {
        while (a[i] != 0) {
            if (y % 2 == 0) {
                auto n_paint = min(W - x, a[i]);
                for (int j = x; j < x + n_paint; ++j) grid[y][j] = i;
                a[i] -= n_paint;
                x += n_paint;
                if (x == W) y++, x = W - 1;
            }
            else {
                auto n_paint = min(x + 1 - 0, a[i]);
                for (int j = x; j > x - n_paint; --j) grid[y][j] = i;
                a[i] -= n_paint;
                x -= n_paint;
                if (x == -1) y++, x = 0;
            }
        }
    }

    for (int r = 0; r < H; ++r) {
        for (int c = 0; c < W; ++c) {
            cout << grid[r][c] << " ";
        }
        cout << endl;
    }
    return 0;
}

Measured memory_bytes: 384
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define rep(i, N) for(ll i = 0; i < (ll)N; i++)
typedef long long ll;
#define MOD 1000000007
#define min(l,r) ((l)<(r)?l:r)

int main() {
    int n, m, ans = MOD, flag = 0;
    char s[1010],t[1010];
    scanf("%s%s", s,t);
    int r = strlen(s) - (int)strlen(t) +1;
    int l = (int)strlen(t);
    int tmp;
    rep(i,r){
        tmp = 0;
        rep(j,l){
            if(s[i+j] != t[j]) tmp++;
        }
        ans = min(ans, tmp);
    }

    printf("%d\n",ans);
}


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

using namespace std;

int main(){
	string str;
 	cin >> str;
  	int a, b;
  	a = (str[0] - '0') * 10 + str[1] - '0';
  	b = (str[2] - '0') * 10 + str[3] - '0';
  	if(0 < a && a < 13 && 0 < b && b < 13){
	    cout << "AMBIGUOUS" << endl;
    }else if(0 < a && a < 13){
    	cout << "MMYY" << endl;
    }else if(0 < b && b < 13){
    	cout << "YYMM" << endl;
    }else{
    	cout << "NA" << endl;
    }

	return 0;
}

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

#ifdef __linux
#define _U(s) s##_unlocked
#else
#define _U(s) _##s##_nolock
#define _CRT_DISABLE_PERFCRIT_LOCKS
#endif
#define gcu _U(getchar)
#define pcu _U(putchar)
#define _DEF(r, n, ...) inline r n(__VA_ARGS__) noexcept
#define _T template <typename T>
#define _HT template <typename H,typename... T>
#define _OP(t) inline operator t()
struct _in {
#ifdef _GLIBCXX_STRING
	_OP(string){string s;for(char c;c=gcu(),c!=' '&&c!='\n'&&c!=EOF;)s+=c;return s;}
#define _S
#endif
	_OP(char){char c=gcu();gcu();return c;}
	_OP(double){double d; scanf("%lf",&d); gcu();return d;}
	_T _OP(T){T n{},m{1},c;if((c=gcu())=='-')m=-1,c=gcu();do{n=10*n+(c-'0'),c=gcu();}while(c>='0'&&c<='9');return m*n;}
} in;
#define _SCAN(...) _DEF(bool,scan,__VA_ARGS__)
#ifdef _S
_SCAN(string &o) {int c{gcu()};if(c==EOF)return false;else{ungetc(c,stdin);string t=move(in);o=t;return true;}}
#endif
_T _SCAN(T &o) {int c{gcu()};return c==EOF?false:(ungetc(c,stdin),o=in,true);}
_HT _SCAN(H &h,T&&... t){return scan(h)&&scan(t...);}
#define _OUT(...) _DEF(void,out,__VA_ARGS__)
#define _OUTL(...) _DEF(void,outl,__VA_ARGS__)
_OUT(bool b){pcu('0'+b);}
_OUT(const char *s){while(*s)pcu(*s++);}
_OUT(char c){pcu(c);}
#ifdef _S
_OUT(string &s){for(char c:s)pcu(c);}
#endif
_T _OUT(T n){static char b[20];char *p=b;T m=n<0?pcu('-'),-1:1;
	if(!n)*p++='0';else while(n)*p++=(char)(n%10*m+'0'),n/=10;while(p!=b)pcu(*--p);}
_OUTL(){out('\n');}
#ifdef _GLIBCXX_VECTOR
	_T _OUT(vector<T> &v){for(T &x:v)out(&x == &v[0]?"":" "),out(x);}
#endif
	_HT _OUT(H &&h, T... t){out(h);out(t...);}
	template <typename... T> _OUTL(T... t){out(t...);outl();}
	struct range{
		int e,b=0,s=1;range(int _b,int _e,int _s):e(_e),b(_b),s(_s){} range(int _b,int _e): e(_e), b(_b){} range(int _e):e(_e){}
		struct it{int v,s; it(int _v,int _s):v(_v),s(_s){} operator int()const{return v;} operator int&(){return v;}int operator*()const{return v;}
			it& operator++(){v+=s;return *this;} }; it begin(){return {b,s};} it end(){return {e,s};}};
#define times(i,n) for(int i=n;i;i--)

int main() {
	int a {in}, b {in};
	outl([&] {
		 times(i, in) {
			 int s {in}, f {in};
			 if (a < f && s < b)
				return 1;
			 }
		 return 0;
	}());
}


Measured memory_bytes: 2632
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        for(int i=0; i<s.length()/2; i++) {
            String s1 = s.substring(i, i+1);
            String s2 = s.substring(s.length() -i -1, s.length() -i);
            if(!s1.equals(s2)) {
                System.out.println("No");
                return;
            }
        }
        String s3 = s.substring(0,(s.length() -1) /2);
        for(int i=0; i<s3.length()/2; i++) {
            String s1 = s3.substring(i, i+1);
            String s2 = s3.substring(s3.length() -i -1, s3.length() -i);
            if(!s1.equals(s2)) {
                System.out.println("No");
                return;
            }
        }
        String s4 = s.substring((s.length() +1) /2, s.length());
        for(int i=0; i<s4.length()/2; i++) {
            String s1 = s4.substring(i, i+1);
            String s2 = s4.substring(s4.length() -i -1, s4.length() -i);
            if(!s1.equals(s2)) {
                System.out.println("No");
                return;
            }
        }
        System.out.println("Yes");
    }
}

Measured memory_bytes: 23636
use std::io;

fn bin_search(target: &Vec<u64>, val: u64) -> bool {
    let mut st = 0;
    let mut end = target.len()-1;
    while st <= end {
        let idx = (end+st) / 2;
        if target[idx] == val {
            return true;
        } else if target[idx] < val {
            st = idx + 1;
        } else {
            end = idx - 1;
        }
    }
    false
}

/// 二分探索による調査。targetは昇順に整列済みであるとする
fn search_same(target: &Vec<u64>, src: &Vec<u64>) -> u32 {
    let mut cnt = 0;
    for v in src {
        if bin_search(target, *v) {
            cnt += 1;
        }
    }
    cnt
}

fn main() {
    let sin = io::stdin();
    
    let mut buf = String::new();
    sin.read_line(&mut buf).ok();
    let _n: usize = buf.trim().parse().unwrap();

    let mut buf = String::new();
    sin.read_line(&mut buf).ok();
    let s = buf.split_whitespace()
        .map(|v| v.parse::<u64>().unwrap())
        .collect::<Vec<u64>>();

    let mut buf = String::new();
    sin.read_line(&mut buf).ok();
    let _q: usize = buf.trim().parse().unwrap();

    let mut buf = String::new();
    sin.read_line(&mut buf).ok();
    let t = buf.split_whitespace()
        .map(|v| v.parse::<u64>().unwrap())
        .collect::<Vec<u64>>();

    println!("{}", search_same(&s, &t));
}



Measured memory_bytes: 7068
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef double D;
typedef long double LD;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> opset;
#define SZ(X) ((int)X.size())
#define ALL(I) I.begin(), I.end()
#define PB push_back
#define F first
#define S second
#define MP make_pair
#define eps 1e-12
#define INF 1000000007
#define MXN 105
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)

int n, pa[MXN], ans;
int fd(int x){
	return x == pa[x] ? x : pa[x] = fd(pa[x]);
}

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++) pa[i] = i;
	if(n & 1){
		for(int i = 1; i <= n / 2; i ++) pa[i] = pa[fd(n - i)];
	} else {
		for(int i = 1; i <= n / 2; i ++) pa[i] = pa[fd(n + 1 - i)];
	}
	for(int i = 1; i <= n; i ++){
		for(int j = i + 1; j <= n; j ++){
			if(fd(i) != fd(j)) ans ++;
		}
	}
	printf("%d\n", ans);
	for(int i = 1; i <= n; i ++){
		for(int j = i + 1; j <= n; j ++){
			if(fd(i) != fd(j)) printf("%d %d\n", i, j);
		}
	}
}



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

using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long int

int main(){
  vector<int> arr;
  map<int,int>m;
  arr.push_back(1);
  for(int i=2;i<=1000;i++){
    int a=0;
    for(int j=2;a<=1000;j++){
      a=1;
      for(int k=0;k<j;k++){
	a*=i;
      }
      if(!m[a]){
      arr.push_back(a);
      m[a]++;
      }
    }
  }
  sort(arr.begin(),arr.end());
  int p=0;
  int x;
  cin>>x;
  //  rep(i,arr.size())
  //cout<<arr[i]<<endl;
  while(arr[p]<=x){
    p++;
  }
  if(x==1)
    cout<<1<<endl;
  else
  cout<<arr[p-1]<<endl;

  return 0;
}


Measured memory_bytes: 256
import math
def fact(n):
    return math.factorial(n)

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

if abs(N-M) >= 2:
    print(0)
    exit()

mod = int(1e9)+7

if N == M:
    print(2*fact(N)*fact(M)%mod)
else:
    print(fact(N)*fact(M)%mod)

Measured memory_bytes: 5172
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <string>
#include <map>
#include <stack>
using namespace std;
typedef long long int lli;
#define urept(soeji, start, n) for (int soeji = start; soeji < n; soeji++)
#define drept(soeji, start, n) for (int soeji = start; soeji > n; soeji--)
int main(void)
{
    int N;
    cin >> N;
    int tmp;
    vector<int> a, b;
    for (int i = 0; i < N; i++)
    {
        cin >> tmp;
        a.push_back(tmp);
    }
    b = a;
    sort(b.begin(), b.end());
    if (b[0] != 1)
    {
        cout << -1 << endl;
        return 0;
    }
    else
    {
        int now = 1;
        int cnt = 0;
        int idx = 0;
        for (int i = 0; i < N; i++)
        {
            if (a[i] == 1)
            {
                idx = i;
                break;
            }
        }
        for (int i = 0; i < N; i++)
        {
            if (a[i] == now + 1 && i > idx)
            {
                now = a[i];
                idx = i;
            }
            else
            {
                if (a[i] == now && idx == i)
                {
                }
                else
                {
                    cnt++;
                }
            }
        }
        cout << cnt << endl;
    }
    return 0;
}


Measured memory_bytes: 4996
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <deque>
#include <algorithm>
#include <iomanip>
#include <functional>
#include <numeric>
#include <sstream>

#define REP(i, n) for(int i = 0;i < (n); i++)
#define REP2(i, x, n) for(int i = (x); i < (n); i++)
#define RREP(i, n) for (int i = (n) - 1;i >= 0; i--)

#define ALL(a) (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define DESCSORT(c) sort(c.begin(), c.end(), greater<int>())

#define LL long long int
#define LD long double

#define PI 3.14159265358979

using namespace std;

//================================================

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

	LL N;
	while (cin >> N) {
		if (N == 0) return 0;

		int ans = 0;
		while (N >= 5) {
			N /= 5;
			ans += N;
		}

		cout << ans << "\n";
	}
	return 0;
}

Measured memory_bytes: 3124
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;

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

    int W_Left = 0; int R_Right = 0;
    int minMoves = INT_MAX;

    for(int i = 0 ; i < n; i++)
    {
        if(s[i] == 'R')
        R_Right++;
    }

    for(int i = 0 ; i < n ; i++)
    {
        minMoves = min(minMoves, max(W_Left, R_Right) );
        if(s[i] == 'W') W_Left++;
        else if(s[i] == 'R') R_Right--;
    }

    minMoves = min(minMoves, max(W_Left, R_Right) );

    cout << minMoves;
}

Measured memory_bytes: 3696
import java.util.*;

public class Main{
    public static void main(String args[]){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long a[] = new long[n];
        for (int i = 0; i < n; ++i){
            a[i] = in.nextLong();
        }


        for (int i = 0; i < n-1; ++i){
            if (a[i] < 0){
                a[i] = a[i]*(-1);
                a[i+1] = a[i+1]*(-1);
            }
        }
        Arrays.sort(a);
        if (Math.abs(a[0]) > a[1]){
            a[0] = a[0]*(-1);
            a[1] = a[1]*(-1);
        }

        long sum = 0;

        for (int i = 0; i < n; ++i){
            sum += a[i];
        }
        System.out.println(sum);
    }
}


Measured memory_bytes: 48916
import java.util.*;


public class Main {
    public static void main(String[] args) {
        // 自分の得意な言語で
        // Let's チャレンジ！！

        Scanner sc = new Scanner(System.in);
int n;
List<String> array = new ArrayList<String>();
n=sc.nextInt();
sc.nextLine();
for(int i=0;i<n;i++)
array.add(sc.nextLine());
Collections.sort(array);
for(int i=0;i<n;i++)
System.out.print(array.get(i));
}}

Measured memory_bytes: 22996
#include <deque>
#include <iostream>
#include <numeric>

using namespace std;
using ll = long long;

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

  deque<ll> q(9);
  iota(q.begin(), q.end(), 1);

  ll x;
  for (auto i = 1; i != k; ++i) {
    x = q.front();
    q.pop_front();

    const auto xmod10 = x % 10;
    if (xmod10) q.push_back(10 * x + xmod10 - 1);
    q.push_back(10 * x + xmod10);
    if (xmod10 != 9) q.push_back(10 * x + xmod10 + 1);
  }

  cout << q.front() << endl;

  return 0;
}


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

int main(){
  int a,b,x; cin >>a >>b >>x;
  if(a*a*b>=2*x) cout <<fixed<<setprecision(10)<<atan(a*b*b/2.0/x)*180/acos(-1);
  else cout <<fixed<<setprecision(10)<<atan((2.0*b-2.0*x/a/a)/a)*180/acos(-1);
return 0;}

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

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

typedef long long ll;
typedef array<int, 3> tri;
typedef long double ld;

template <class T> istream& operator>>(istream& I, vector<T>& v) {for (T &e: v) I >> e; return I;}
template <class T> ostream& operator<<(ostream &O, const vector<T>& v) {for (const T &e: v) O << e << ' '; return O;}



void _main() {
        int n; cin >> n;
        vector<int> v(n); cin >> v;
        vector<int> c(n); cin >> c;
        int ans = 0;
        for (int mask = 0; mask < (1 << n); mask++) {
                int x = 0, y = 0;
                for (int bit = 0; bit < n; bit++) {
                        if (1 << bit & mask) {
                                x += v[bit];
                                y += c[bit];
                        }
                }
                ans = max(ans, x - y);
        }

        cout << ans;
}



signed main() {
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//        freopen("input.txt", "r", stdin);
        int _t = 1;
//        cin >> _t;
        while (_t--) _main();
        return 0;
}


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


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

    string ans = "";

    while( N!=0 ){
        if( N%2 != 0){
            N = N - 1;
            ans = "1" + ans;
        }else {
            ans = "0" + ans;
        }

        N = N / (-2);
    }

    if(ans == ""){
        ans = "0";
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 384
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cassert>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <cassert>
#include <string.h>

using namespace std;

int main()
{
	int a,b;
	cin >> a>>b;
	int res;
	if (a == b){
		cout << a+b <<endl;
		return 0;
	}
	
	else {
		//int res = std::max(a,b) + std::max(a,b)-1; 
		res =  2*max(a,b) - 1;
	}
	
	cout << res <<endl;
	
	
	
	
	
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int sub(char c) {
    switch(c) {
        case '0': return 0;
        case '1': return 1;
        case '2': return 2;
        case '3': return 3;
        case '4': return 4;
        case '5': return 5;
        case '6': return 6;
        case '7': return 7;
        case '8': return 8;
        case '9': return 9;
        default : return -1;
    }
}

int main(){
    string x;
    for (int i=0;i<i+1;i++) {
        cin >> x;
        if ( x != "0" ) {
            int sum = 0;
            int l = x.length();
            for (int j=0;j<l;j++) {
                char c = x.at(j);
                int C = sub(c);
                sum = sum + C;
            }
            cout << sum << endl;
        } else {
            break;
        }
    }
    
}



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

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>
#include<iomanip>
#include<unordered_set>
#include<bitset>
#include<complex>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

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

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD =  (int)1e9 + 7;
const double EPS = 1e-9;

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

	int N;
	cin >> N;
	map<pii, int> pmap;
	rep(i, 1, N + 1)
	{
		string S = to_string(i);
		int a = S.front() - '0';
		int b = S.back() - '0';
		if (b == 0)continue;
		pmap[mp(a,b)]++;
	}

	int ans = 0;
	for (auto p : pmap)
	{
		ans += p.second*pmap[mp(p.first.second, p.first.first)];
	}

	cout << ans << endl;

	return 0;
}

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

#include<cstdio>
#define r(i,n) for(int i=0;i<n;i++)

int main(void){
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  cout<<min(a,b)+min(c,d)<<endl;


return 0;}


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

const int N = 1e5 + 7;
vector <pair <int, int>> g[N];
int sz[N];
 
ll ans = 0;
 
int n;
 
bool ok = false; 
 
int mn = 1e9;

void dfs(int u, int p) {
    sz[u] = 1;
    for (auto pr : g[u]) {
        int v = pr.first, w = pr.second;
        if (v != p) {
            dfs(v, u);
            sz[u] += sz[v];
            int a = sz[v];
            int b = n - sz[v];
            if (a != b) {
                ans += (2LL * min(a, b)) * w;
            } else {
                ans += (2LL * min(a, b) - 1) * w;
                ok = true;
            }
        }
    }
    bool good = (2 * (n - sz[u])) < n;
    for (auto pr : g[u]) {
        int v = pr.first, w = pr.second;
        if (v != p) {
            good &= (2 * sz[v]) < n;
        }
    }
    if (good) {
        for (auto pr : g[u]) {
            int v = pr.first, w = pr.second;
            mn = min(mn, w);
        }
    }
} 

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.setf(ios::fixed); cout.precision(20);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    cin >> n;
    for (int i = 0; i + 1 < n; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    dfs(0, -1);
    if (!ok) ans -= mn;
    cout << ans << '\n';
}

Measured memory_bytes: 14208
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    vector<string> a(n),b(m);
    for(int i=0; i<n; i++) cin>>a[i];
    for(int i=0; i<m; i++) cin>>b[i];
    for(int i=0; i<n-m+1; i++){
        for(int j=0; j<n-m+1; j++){
            bool ok=true;
            for(int k=0; k<m; k++){
                for(int l=0; l<m; l++){
                    if(a[i+k][j+l]!=b[k][l]) ok=false;
                }
            }
            if(ok){
                cout<<"Yes"<<endl;
                return 0;
            }
        }
    }
    cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
 
using namespace std;
#define ff first
#define ss second
#define pii pair<int, int>
#define pll pair<long long , long long>
#define pb push_back
#define ll long long
#define ld long double
#define precision(x,d) cout<<fixed<<setprecision(d)<<x
#define fill(a,b) memset((a),(b),sizeof((a)))
#define FAST ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);srand(time(NULL));
ll power(ll x,ll y,ll m){ll r=1;for(;y;y>>=1){if(y&1)r=r*x%m;x=x*x%m;}return r;}
const ll mod = 1e9 + 7;
const ld pi = 3.14159265358979;
 
int run_test(){
    ld a, b, h, m;
    cin >> a >> b >> h >> m;
    precision(sqrt(a*a + b*b - 2*a*b*cos((60*h*pi - 11*m*pi)/360)), 10);
    return 0;
}
 
int main(){
    FAST;
    ll t;
    t = 1;
 
    while(t--){
        run_test();
    }
}

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

using namespace std;

template <typename T> T gcd(T x, T y) {
  if (y == 0)
    return x;
  return gcd(y, x % y);
}

template <typename T> T lcm(T x, T y) {
  if (x == 0 || y == 0)
    return 0;
  return x / gcd(x, y) * y;
}

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

  int M;
  cin >> M;
  for (int i = 0; i < M; i++) {
    cin >> tmp;
    s[tmp]--;
  }
  int ma = 0;
  for (auto x : s) {
    ma = max(ma, x.second);
  }
  cout << ma << endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int main()
{
  int i, n;
  int sum, hit;

  while (1) {
    scanf("%d", &n);
    if (n == 0) {
      break;
    }
    sum = 0;
    for (i = 0; i < n/4; i++) {
      scanf("%d", &hit);
      sum += hit;
    }
    printf("%d\n", sum);
  }

  return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, N) for (int i = 0; i < (int)N; i++)
#define all(a) (a).begin(), (a).end()

int N, X, Y;
vector<int> a;

int main () {
  cin >> N >> X >> Y;
  a.resize(N);

  rep(i,N) cin >> a[i];

  int ans = abs(a[N-1] - Y);
  if(N > 1) ans = max(ans, abs(a[N-1] - a[N-2]));
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
 int a,b;
 scanf("%d",&a);
 scanf("%d",&b);
 if(a>b)
 {
 	printf("a > b\n");
 }
 if(a<b)
 {
 	printf("a < b\n");
 }
 if(a==b)
 {
 	printf("a == b\n");
 }

	return 0;
}

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

int main(){
  int x; cin >>x;
  for(int i=-54; i<120; i++)
  {
    for(int j=-54; j<120; j++)
    if(i*i*i*i*i-j*j*j*j*j==x){cout <<i<<" "<<j; return 0;}
  }
}

Measured memory_bytes: 3604
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>

#define REP(i,n) for(int i=0;i<n;++i)
#define REPR(i,n) for(int i=n;i>=0;--i)
#define REPI(itr,v) for(auto itr=v.begin();itr!=v.end();++itr)
#define REPIR(itr,v) for(auto itr=v.rbegin();itr!=v.rend();++itr)
#define FOR(i,a,b) for(int i=a;i<b;++i)
#define SORT(v,n) sort(v, v+n)
#define SORTV(v) sort(v.begin(), v.end())
#define ALL(v) v.begin(),v.end()
#define llong long long
#define INF 999999999
#define SUR 1000000007
#define pb(a) push_back(a)
#define pf(a) push_front(a)
#define MP make_pair
#define SV(n,v) {int tmp;for(int i=0;i<n;++i){scanf("%d", &tmp);v.push_back(tmp);}}
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

using namespace std;

typedef pair<int,int> pii;

int main(){

  string s;
  cin >> s;

  int ans = 0;
  REP(i,s.length()){
    if(s[i] == '1'){
      ans++;
    }
  }

  cout << ans << endl;
  return 0;
}



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

using namespace std;

typedef long long ll;

int main () {
  int n;
  cin >> n;
  vector<int> b(n - 1);
  for (int i = 0; i < n - 1; ++i) cin >> b[i];
  vector<int> a(n);
  for (int i = 0; i < n - 1; ++i) {
	  a[i] = b[i];
  }
  a[n-1] = 100001;
  for (int i = 0; i < n - 1; ++i) {
	  a[i + 1] = min(a[i+1], b[i]);
  }
  int ans = 0;
  for (auto x  : a) {
	  ans += x;
  }
  cout << ans;
}


Measured memory_bytes: 256
#include<iostream>
#include<cassert>
#include<vector>
#include<algorithm>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
const double eps = 1e-10;
class Info{
public:
  double s,e,c,time;
  double consume;
  Info(){};
  Info(double ts,double te,double tc){
    s=ts;
    e=te;
    c=tc;
    consume=e-s;
    consume*=c;
    time=e-s;
  };
};

double can_water(vector<Info >in,double L,double p,double ini){
  double vol=ini;
  double lasttime=0;//last time that scheduled
  rep(i,in.size()){
    vol=vol+(in[i].s-lasttime)*p;
    vol=min(L,vol);
    vol=vol+in[i].time*p-in[i].consume;
    if ( vol<=eps)return -1;
    vol=min(vol,L);
    lasttime=in[i].e;
  }

  vol=vol+(86400-lasttime)*p;
  vol=min(vol,L);
  return vol;
}

double solve(vector<Info > in,double L){
  double mini=0,maxi=100000000,ret=0,mid;
  while(mini+eps<maxi){
    double mid = (mini+maxi)/2;
    double day1=can_water(in,L,mid,L);
    if ( day1<=0){mini=mid+eps;continue;}
    
    double day2 = can_water(in,L,mid,day1);
    if (day2>0 && day2-day1>=0)maxi=mid-eps,ret=mid;
    else mini=mid+eps;
  }

  return ret;
}

main(){
  int n;
  double L;
  while(cin>>n>>L&&n){
    vector<Info> in;
    double s,t,c;
    rep(i,n){
      cin>>s>>t>>c;
      in.push_back(Info(s,t,c));
    }
    printf("%.8lf\n",solve(in,L));
  }
}

Measured memory_bytes: 10000
#include <iostream>
#include <algorithm>
using namespace	std;
int main(){

  long long n,t1,t2;
  cin>>n>>t1;
  for(int i=1;i<n;i++){
    cin>>t2;
    long long gcd=__gcd(t1,t2);
    if(t1%gcd==0) t1/=gcd;
    else t2/=gcd;
    t1=t1*t2;
  }
  cout<<t1<<endl;
  return 0;

}




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

int main() {
    int ans = 1;
    int N;
    string S;
    cin >> N >> S;
    char s = S[0];
    for(size_t i = 1; i < N; i++) {
        if(s != S[i]) {
            ans++;
            s = S[i];
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 512
#include<stdio.h>
int main(){
  double total=0;
  int i;
  int n;
  scanf("%d",&n);
  double x[15];
  char y[5][15];
  for(i=0;i<n;i++){
    scanf("%lf",&x[i]);
    scanf("%s",y[i]);
    if(y[i][0]=='J'){
      total+=x[i];
    }else if(y[i][0]=='B'){
      x[i]=x[i]*380000;
      total+=x[i];
    }

  }

  printf("%lf",total);

}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define INF 2 << 29
#define MOD 1000000007
#define Yes(f) puts((f)? "Yes" : "No")
#define YES(f) puts((f)? "YES" : "NO")
#define pi 3.1415926535897
int gcd(int a, int b) {
	if (b != 0) return gcd(b, a % b);
	return a;
}
int lcm(int a, int b) {
	return a / gcd(a, b) * b;
}

using Graph = vector<vector<int>>;

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

Measured memory_bytes: 3600
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int D,cnt[19],ans;ll b[20];
void dfs(int x,ll res,int L,int now)
{
    if(x>(L>>1)-1){if(res==D) ans+=now*(L&1?10:1);return;}
    ll i=-9ll;while(i<9ll&&res+(i+1ll)*(b[L-x-1]-b[x])<=D) ++i;
    dfs(x+1,res+i*(b[L-x-1]-b[x]),L,now*(x==0&&i>=0?cnt[i+9]-1:cnt[i+9]));
    if(++i<=9) dfs(x+1,res+i*(b[L-x-1]-b[x]),L,now*(x==0&&i>=0?cnt[i+9]-1:cnt[i+9]));
}
int main()
{
    scanf("%d",&D);
    b[0]=1ll;for(int i=1;i<19;++i) b[i]=b[i-1]*10ll;
    for(int i=0;i<=9;++i) for(int j=0;j<=9;++j) ++cnt[i-j+9];
    for(int i=1;i<=18;++i) dfs(0,0,i,1);
    printf("%d",ans);
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main()
{
	int k;
	char s[101];

	scanf("%d%s",&k,s);

	if(strlen(s)<=k)
		printf("%s\n",s);
	else{
		for(int i=0;i<k;i++)
			printf("%c",s[i]);
		printf("...\n");
	}
	return 0;
}

Measured memory_bytes: 1648
macro_rules! input {
     (source = $s:expr, $($r:tt)*) => {
         let mut iter = $s.split_whitespace();
         input_inner!{iter, $($r)*}
     };
     ($($r:tt)*) => {
         let s = {
             use std::io::Read;
         let mut s = String::new();
         std::io::stdin().read_to_string(&mut s).unwrap();
         s
     };
     let mut iter = s.split_whitespace();
     input_inner!{iter, $($r)*}
     };
}
     
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
 
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}
 
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
 
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
 
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
 
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
 
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_imports)]
use std::io::{stdout, Write, BufWriter};
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
//#[allow(unused_imports)]
//use proconio::marker::{Isize1, Usize1, Bytes, Chars};
//#[proconio::fastout]
use std::collections::VecDeque;
fn main() {
    input!{
        s: String,
        t: String,
    }
    let mut s: VecDeque<char> = s.chars().collect();
    let t: VecDeque<char> = t.chars().collect();
    for _ in 0..s.len() {
        if s == t {
            println!("Yes");
            return;
        }
        let last = s.pop_back().unwrap();
        s.push_front(last);
    }
    println!("No");
}


Measured memory_bytes: 4352
/*
 * main.c
 *
 *  Created on: 2020/03/28
 *      Author: family
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MAX(a,b) (a > b ? a : b)
#define MIN(a,b) (a > b ? b : a)
typedef long long int ll;
typedef unsigned long long int ull;

int sort_inc(const void *a, const void *b) { return (*(int*)a - *(int*)b);}
int sort_dec(const void* a, const void* b) { return (*(int*)b - *(int*)a);}
int sort_dec_ll(const void *a, const void *b) {
    ll da = *(ll*)a, db = *(ll*)b;    int val = 0;
    if(da > db) { val = -1; }
    else if (da == db) { val = 0; }
    else { val = 1; }
    return val;
}
int sort_inc_ll(const void *a, const void *b) {
    ll da = *(ll*)a, db = *(ll*)b;    int val = 0;
    if(da > db) { val = 1; }
    else if (da == db) { val = 0; }
    else { val = -1; }
    return val;
}
int sort_dic(const void *a, const void *b) {
    char *pa = (char *)a;    char *pb = (char *)b;    int i = 0, val = 0, N = 10;
    for (i = 0; i < N; i++) {
    	char da = pa[i], db = pb[i];
    	if (da == db) continue;
  		if (da > db) val = 1; else val = -1;
        break;
    }
    return val;
}

void yesno(int ans) {
	if (ans == 1) {
		printf("Yes\n");
	} else {
		printf("No\n");
	}
	return;
}

char S[200001][11] = {0};
int s[200001] = {0};
int main()
{
	ll N = 0, ans = 0;
	ll i = 0, j = 0;
	memset(S, 0, sizeof(S));
	scanf("%lld", &N);
	for (i = 0; i < N; i++) {
		scanf("%s", &S[i][0]);
	}
	qsort(S, N, sizeof(char)*11, sort_dic);
	s[0]++;
	for (i = 1; i < N; i++) {
		//printf("%s\n", S[i]);
		if (strcmp(S[i-1], S[i]) == 0) {
			s[j]++;
		} else {
			j++;
			s[j]++;
		}
	}
	for (i = 0; i < N; i++) {
		if (s[i] != 0) {
			ans++;
		}
	}
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 5716
#include<stdio.h>
int MAX(int a,int b){return a<b?b:a;}
int ta[100010],nt[200010],to[200010],co[200010],g;
int bfs(int v,int s){
  int q[1000000],C[100010],t=0,r=1,i,max=0;
  for(i=0;i<v;i++)C[i]=1000000000;
  for(C[q[0]=s]=0;r-t;t++){
    for(i=ta[q[t]];i+1;i=nt[i]){//printf("%d %d %d\n",q[t],to[i],co[i]);
      if(C[to[i]]>C[q[t]]+co[i])C[q[r++]=to[i]]=C[q[t]]+co[i];
      if(max<C[to[i]])max=C[g=to[i]];//printf("m%d\n",max);
    }
  }
  return max;
}//*/
int tyokkei(int v,int e,int *a,int *b,int *c){
  int i,max=0,j;
  for(i=0;i<v;i++)ta[i]=-1;
  for(i=0;i<e;i++){
    nt[i  ]=ta[to[i+e]=a[i]];
    nt[i+e]=ta[to[i  ]=b[i]];
    //nt[i  ]=ta[a[i]];
    //to[i  ]=b[i];
    //co[i  ]=c[i];
    //ta[a[i]]=i;
    //nt[i+e]=ta[b[i]];
    //to[i+e]=a[i];
    //co[i+e]=c[i];
    //ta[b[i]]=i+e;
    //nt[i  ]=ta[to[i+e]=a[i]];
    //nt[i+e]=ta[to[i  ]=b[i]];
    co[ta[b[i]]=i+e]=co[ta[a[i]]=i]=c[i];
  }
  /*for(i=0;i<v;i++){printf("%d:",i);
    for(j=ta[i];j+1;j=nt[j])printf("%d ",to[j]);printf("\n");
    }//*/
  bfs(v,0);
  return bfs(v,g);
}
int main(){
  int n,a[100010],b[100010],c[100010],i;
  scanf("%d",&n);
  for(i=0;i<n-1;i++)scanf("%d %d %d",&a[i],&b[i],&c[i]);
  printf("%d\n",tyokkei(n,n-1,a,b,c));
  return 0;
}

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

string dp[50][500];

struct edge {
	int to;
	string s;
};

struct S {
	int v;
	string s;

	bool operator <(const S& x) const {
		return s > x.s;
	}
};

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

	int n, a, s, g;
	while(cin >> n >> a >> s >> g, n) {
		vector<edge> G[50];
		for(int i = 0; i < a; i++) {
			int x, y;
			string str;
			cin >> x >> y >> str;
			G[x].push_back({ y, str });
		}

		for(int i = 0; i < n; i++) {
			for(int j = 0; j < 400; j++) {
				dp[i][j] = "{";
			}
		}

		priority_queue<S> q;
		q.push({ s, "" });
		dp[s][0] = "";
		while(q.size()) {
			int v = q.top().v;
			string str = q.top().s;
			q.pop();
			if(dp[v][str.size()] < str) continue;

			//cerr << "v : " << v << ", t : " << t << ", str : " << str << endl;
			if(str.size() >= 400) continue;

			for(auto e : G[v]) {
				string ns = str + e.s;
				if(ns.size() >= 400) continue;
				if(dp[e.to][ns.size()] > ns) {
					dp[e.to][ns.size()] = ns;
					q.push({ e.to, ns });
				}
			}
		}

		string ans = "{";
		for(int i = 1; i < 300; i++) {
			if(dp[g][i] == "{") continue;

			bool flag = true;
			for(int j = i + 1; j < 400; j++) {
				if(dp[g][i] > dp[g][j]) {
					flag = false;
					break;
				}
			}
			if(flag) {
				ans = dp[g][i];
				break;
			}
		}
		if(ans == "{") cout << "NO" << endl;
		else cout << ans << endl;
	}
}

Measured memory_bytes: 21880
fun main(args: Array<String>) {
    // 与えられた入力をスペースで区切った配列にする
    val S: String = readLine()!!

    // 前半２文字
    val startString: String = S.substring(0, 2)
    val startNumber: Int = startString.toInt()

    // 後半２文字
    val endString: String = S.substring(2, 4)
    val endNumber: Int = endString.toInt()

    var yymmFlag = false
    var mmyyFlag = false

    // YYMM が成立するかどうか
    if (endNumber > 0 && endNumber <= 12) {
        yymmFlag = true
    }

    // MMYY が成立するかどうか
    if (startNumber > 0 && startNumber <= 12) {
        mmyyFlag = true
    }

    if (yymmFlag && mmyyFlag) {
        println("AMBIGUOUS")
    } else if (yymmFlag) {
        println("YYMM")
    } else if (mmyyFlag) {
        println("MMYY")
    } else {
        println("NA")
    }
}

Measured memory_bytes: 31700
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define vpll vector <pll>
#define pb push_back
#define f(i,a,n) for(ll i=a;i<n;i++)
const ll N=2e5;

int main()
{
    ll a,b,c,k;
    cin>>a>>b>>c>>k;
    if(a>=k) cout<<k;
    else if((a+b)>=k) cout<<a;
    else cout<<a-(k-a-b);
    return 0;
}



Measured memory_bytes: 3572
/**
 * Combinatorial - 0-1 Knapsack Problem
 */

#include <iostream>

using namespace std;

int main() {

    int N, W;
    int vs[101];
    int ws[101];
    int dp[101][10001];

    cin >> N >> W;

    for (int i = 1; i <= N; i++) {
        int v, w;
        cin >> v >> w;
        vs[i] = v;
        ws[i] = w;
    }

    fill(dp[0], dp[101], 0);

    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= W; j++) {
            if (j < ws[i]) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - ws[i]] + vs[i]);
            }
        }
    }

    cout << dp[N][W] << endl;
}

Measured memory_bytes: 7040
// https://atcoder.jp/contests/ddcc2020-qual/tasks/ddcc2020_qual_b
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i, n) FOR(i, 0, n)
#define REPR(i, n) for (int i = n - 1; i >= 0; i--)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
#define DIV(a, b) ((a - 1) / b + 1)

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    vector<int> A(N);
    for (auto &x : A) {
        cin >> x;
    }
    int sum = accumulate(ALL(A), 0LL);
    int ans = 1e10, t = 0;
    REP(i, N) {
        t += A[i];
        ans = min(ans, abs(sum - 2 * t));
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1792
#標準入力
a,b = map(int,input().split())
num = list(map(int,input().split()))

#リストの値を全て合計する
num = sum(num)

#出力
if num % (a + 1) == 0:print(num // (a + 1))
else:print(num // (a + 1) + 1)


Measured memory_bytes: 5596
#include <bits/stdc++.h>
using namespace std;
#define Lim 9999991
#define Jmp 1000003

int dic[Lim];

int toint(string s) {
    int ret = 0;
    for (int i = 0; i < s.size(); ++i) {
        ret *= 5;
        switch (s[i]) {
            case 'A':
                ret += 1;
                break;
            case 'T':
                ret += 2;
                break;
            case 'G':
                ret += 3;
                break;
            case 'C':
                ret += 4;
                break;
        }
    }
    return ret;
}

void push(string s) {
    int a = toint(s);
    int i = a % Lim;
    while (true) {
        if (!dic[i]) {
            dic[i] = a;
            return;
        }
        i = (i + Jmp) % Lim;
    }
}

int find(string s) {
    int a = toint(s);
    int i = a % Lim;
    while (true) {
        if (!dic[i]) {
            return 0;
        }
        if (dic[i] == a) {
            return 1;
        }
        i = (i + Jmp) % Lim;
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        string s, t;
        cin >> s >> t;
        if (s == "insert") {
            push(t);
        }
        else {
            if (find(t)) {
                printf("yes\n");
            }
            else {
                printf("no\n");
            }
        }
    }
    return 0;
}

Measured memory_bytes: 31028
#pragma region Macros
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i, n) for(int i=(n); i>=0; --i)
#define FOR(i, n, m) for(int i=(m), i##_len=(n); i<i##_len; ++i)
#define EACH(i, v) for(const auto& i : v)
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<class Value>using vec = vector< Value >;
using ll = long long;
using P = pair< long long, long long >;
#define fi first
#define se second
#define el endl
#pragma endregion
void Main();

int main(){
    std::cin.tie(nullptr);
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}

void Main(){
    int H, W;
    cin >> H >> W;
    vec<vec<bool> > mp(H+2, vec<bool>(W+2));
    vec<string> tx(H+2);
    FOR(i, H+1, 1){
        cin >> tx[i];
        tx[i] = " " + tx[i];
        FOR(j, W+1, 1){
            if(tx[i][j] == '#'){
                mp[i+1][j]
                =mp[i-1][j]
                =mp[i][j+1]
                =mp[i][j-1]
                =true;
            }
        }
    }
    bool ans = true;
    FOR(i, H+1, 1){
        FOR(j, W+1, 1){
            if(tx[i][j] == '#' && !mp[i][j]){
                ans = false;
                cout << "No" << el;return;
            }
        }
    }
    cout << "Yes" << el;
}



Measured memory_bytes: 3544
#include<bits/stdc++.h>
 
using namespace std;
 
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
 
template<typename T>
istream& operator>>(istream &is,vector<T> &v){
    for(auto &it:v)is>>it;
    return is;
}
template<typename T>void chmin(T& a, T& b){a=min(a,b);}
template<typename T>void chmax(T& a, T& b){a=max(a,b);}
 
 
 
namespace BIT_{
    typedef int BITTYPE;
#define BIT_SIZE 1000000
    BITTYPE mem[BIT_SIZE];
};
//[1,n],0は扱えない!
template <typename T>class BIT{
private:
    T* bit;int n;
public:
    BIT(T* _table,int sz,int n)
        :bit(_table),n(n){
        fill(bit,bit+sz,0);
    }
    BIT(int n)
        :BIT(BIT_::mem,BIT_SIZE,n){}
    int sum(int i){
        int s=0;
        while(i>0){
            s+=bit[i];
            i-=i&-i;
        }
        return s;
    }
    int sum(int lb,int ub){
        return sum(ub)-sum(lb-1);
    }
    void add(int i,int x){
        while(i<=n){
            bit[i]+=x;i+=i&-i;
        }
    }
    //v[1]+v[2]+...+v[x]>=wとなる最小のxを求める
    int lowerbound(int w){
        if(w<=0)return 0;
        int x=0;
        for(int k = (1<<(31-__builtin_clz(n)));k >0 ;k>>=1)
            if(x+k<=n&&bit[x+k]<w){
                w-=bit[x+k];
                x+=k;
            }
        return x+1;
    }
    void clear(int sz){
        fill(bit,bit+sz,0);
    }
};
 
typedef vector<int> V;
int get_seq(V &v){
    int n=v.size();
    int res=0;
    BIT<int> b(120000);
    for(auto &it:v){
        res+=b.sum(it+1,120000);
        res%=2;
        b.add(it,1);
    }
    return res;
}
tuple<V,V> get_info(V& v){
    int n=v.size();
    V a,b;
    V min_num(2,0);
    for(int i=0;i<n;i++){
        if(i%2){
            b.push_back(abs(v[i]));
        }
        else{
            a.push_back(abs(v[i]));
        }
        if(v[i]<0)min_num[i%2]++;
    }
    V tem_num(2);
    tem_num[0]=get_seq(a);
    tem_num[1]=get_seq(b);
    return tuple<V,V>(tem_num,min_num);
}
 
typedef long long LL;
int A[3][100000];
int main(){
    int N;
    scanf("%d",&N);
    for(int i=0;i<3;i++)
        for(int j=0;j<N;j++){
            scanf("%d",&A[i][j]);
        }
    for(int i=0;i<N;i++){
        if(A[0][i]==A[1][i]+1&&A[1][i]==A[2][i]+1)continue;
        else
            
        if(A[0][i]==A[1][i]-1&&A[1][i]==A[2][i]-1)continue;
        else{
            printf("No\n");
            return 0;
        }
    }
    V a(N);
    for(int i=0;i<N;i++){
        int x=A[0][i];
        if(x%3==1)a[i]=x/3+1;
        else a[i]=-x/3;
        if(abs(a[i]+1)%2!=i%2){
            printf("No\n");
            return 0;
        }
    }
    V tem_num,min_num;
    tie(tem_num,min_num)=get_info(a);
    if(tem_num[0]%2==min_num[1]%2&&tem_num[1]%2==min_num[0]%2)printf("Yes\n");
    else printf("No\n");
    return 0;
}


Measured memory_bytes: 6396
#!/usr/bin/python3

n = input()

digit = n[-1]

if digit == '2' or digit == '4' or digit == '5' or digit == '7' or digit == '9':
    print('hon')
elif digit == '0' or digit == '1' or digit == '6' or digit == '8':
    print('pon')
else:
    print('bon')






Measured memory_bytes: 61884
#include<stdio.h>
#include<algorithm>
#include<functional>
#include<cmath>
using namespace std;
long long  mod = 1000000007;
int main()
{
	int K, S;
	scanf("%d%d", &K, &S);
	int an = 0;
	for (int i = min(K, S); i >= 0; i--) {
		for (int j = min(K, S - i); j >= 0; j--) {
			if (S - i - j <= K) {
				an++;
			}
		}
	}
	printf("%d", an);
	return 0;
}

Measured memory_bytes: 128
#include <stdio.h>

int main(){
  int i, j, n, list[100], mini, temp, count = 0;

  scanf("%d", &n);

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

  for(i=0; i<n; i++){
    mini = i;
    for(j=i; j<n; j++){
      if(list[j] < list[mini]) mini = j;
    }
    if(i != mini){
      temp = list[i];
      list[i] = list[mini];
      list[mini] = temp;
      count++;
    }
  }

  for(i=0; i<n-1; i++) printf("%d ", list[i]);
  printf("%d\n%d\n", list[i], count);
  
  return 0;
}

Measured memory_bytes: 600