akhauriyash/Code-Regression huggingface dataset:
// inputに入力データ全体が入る
function Main(input) {
	// 1行目がinput[0], 2行目がinput[1], …に入る
	n = input;
	var a=100;
    var year=0;
  
    while(a<n){
    a = Math.floor(a*1.01);
    year=year+1;
    }
	//出力
	console.log(year);
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 29776
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")
    };
}

fn main() {
    ipt_1_2_a();
}

fn ipt_1_2_a(){
    input!{
        a: i32,
        b: i32
    }

    use std::cmp::Ordering;
    
    let text = match a.cmp(&b) {
        Ordering::Less => "a < b",
        Ordering::Equal => "a == b",
        Ordering::Greater => "a > b"
    };
    println!("{}", text)
}


Measured memory_bytes: 5032
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <functional>
#include <vector>
#include <map>
#include <set>
#include <queue>
using _loop_int = int;
#define REP(i,n) for(_loop_int i=0; i<(_loop_int)(n); i++)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a); i<(_loop_int)(b); i++)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1; i>=(_loop_int)(a); i--)
using namespace std;
typedef pair<int,int> P;
typedef long long ll;

const int MOD=1000000007;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;

int main(){
    int count=1, ans=0, start=1, end=1;
    ll K, p=0;
    char c;
    string S;
    cin >> S >> K;
    c = S[0];
    REP(i, S.length()-1){
        if(c == S[i+1]){
            count+=1;
        } else {
            ans += int(count/2);
            count = 1;
        }
        c = S[i+1];
    }
    ans += int(count/2);

    int j=0;
    while(S[j] == S[j+1] & j < S.length()-1){
        start+=1;
        j+=1;
    }
    j=S.length()-1;
    while(S[j] == S[j-1] & j > 0){
        end+=1;
        j-=1;
    }
    if(((start&1)==1) & ((end&1)==1) & (S[0] == S[S.length()-1])){
        p = K-1;
    }

    if(j!=0){
        cout << ans*K + p << endl;
    } else {
        cout << ll(S.length()*K/2) << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
using namespace std;
using Graph = vector<vector<int>>;
typedef long long ll;
typedef pair<int, int> P;
const int inf = 1<<21;
const ll INF = 1LL << 60;
const ll mod = 1e9+7;

int n;
vector<pair<ll, ll>> edges[100001];
bool visited[100001];
int ans[100001];

void solve(int cur, ll cost, int color){
    if(visited[cur]) return;
    visited[cur] = true;
    ans[cur] = cost%2 ? 1-color : color;
    rep(i, edges[cur].size()){
        pair<ll, ll> p = edges[cur][i];
        // if(visited[p.first]) continue;
        solve(p.first, p.second, ans[cur]);
    }
}

int main() {
    cin >> n;
    rep(i, n-1){
        ll from, to, cost;
        cin >> from >> to >> cost;
        from--; to--;
        edges[from].push_back(make_pair(to, cost));
        edges[to].push_back(make_pair(from, cost));
    }
    fill(visited, visited+n, false);
    fill(ans, ans+n, 0);
    solve(0, 0, 0);
    rep(i, n) cout << ans[i] << endl;
    return 0;
}

Measured memory_bytes: 9856
import java.util.Scanner

import scala.annotation.tailrec

object Main {
  def main(args: Array[String]): Unit = {
    //nextLineとnextを同時に使ったら死ぬ
    val sc = new Scanner(System.in)

    val n = sc.nextInt()
    val m = n % 10
    val ans = m match {
      case 2 | 4 | 5 | 7 | 9 => "hon"
      case 0 | 1 | 6 | 8     => "pon"
      case 3                 => "bon"
    }

    println(ans)
  }

  //region

  def debug(args: Any*): Unit = {
    Console.err.println(args.mkString(" "))
    Console.err.flush()
  }

  def printExecTime(process: => Unit): Unit = {
    val start = System.currentTimeMillis
    process
    debug("処理時間： " + (System.currentTimeMillis - start) + " ミリ秒")
  }

  def bitSearch[T](n: Int, choice: Vector[T]): Vector[Vector[T]] = {
    @tailrec
    def bitSearchLogic(n: Int,
                       choice: Vector[T],
                       acc: Vector[Vector[T]]): Vector[Vector[T]] = {
      if (n == 0) acc
      else {
        val newAcc =
          acc.flatMap(vec => {
            choice.map(c => vec :+ c)
          })
        bitSearchLogic(n - 1, choice, newAcc)
      }
    }

    val firstAcc = choice.map(i => Vector(i))
    bitSearchLogic(n - 1, choice, firstAcc)
  }
  //endregion
}


Measured memory_bytes: 55416
#include <bits/stdc++.h>
#define int long long
#define For(i,a,b) for(register int i=a;i<=b;i++)
using namespace std;
int read() {
	register int x=0,f=0;
	register char ch=getchar();
	while(!isdigit(ch)) {
		f|=(ch=='-');
		ch=getchar();
	}
	while(isdigit(ch)) {
		x=x*10+ch-'0';
		ch=getchar();	
	}
	return f?-x:x;
}
void write(int x) {
	if(x<0) {
		putchar('-');
		x*=-1;
	}
	if(x>=10) write(x/10);
	putchar(x%10+'0');
}
int n,m;
signed main() {
	cin>>n>>m;
	if(n>m) swap(n,m);
	int near=m-m%2019;
	if(near>=n) puts("0");
	else {
		int ans=2019;
		For(i,n%2019,m%2019)
			For(j,i+1,m%2019)	
				ans=min(ans,i*j%2019);
		cout<<ans;
	}
	return 0;
}

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

int main() {

    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);

    long long dif = -1;
    string s;
    cin>>s;
    for (int i=0; i<s.length()-2; i++) {
        long long n = 0;
        for (int j=0; j<3; j++) {
            n = 10*n + (s[j+i]-'0');
        }
        if (dif == -1) dif = abs(n - 753);
        else dif = min(dif, abs(n - 753));
    }

    cout<<dif;

    return 0;
}


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

#define int long long
const int mod = 1e9 + 7;

signed main() {
    int N, K;
    cin >> N >> K;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    
    int dp[N+1][K+1];
    for (int i = 0; i < N+1; i++) {
        for (int j = 0; j < K+1; j++) {
            dp[i][j] = 0;
        }
    }
    dp[0][0] = 1;

    for (int i = 1; i < N+1; i++) {
        vector<int> cs(K+2);
        for (int k = 0; k < K+1; k++) {
            cs[k+1] = (cs[k] + dp[i-1][k]) % mod;
        }
        for (int j = 0; j < K+1; j++) {
            dp[i][j] = (cs[j+1] - cs[max(j-A[i-1], 0LL)] + mod) % mod;
        }
    }
    cout << dp[N][K] << endl;
}

Measured memory_bytes: 79984
#include <bits/stdc++.h>
using std::cerr;using std::cin;using std::cout;using std::abs;using std::min;using std::max;using std::swap;using std::map;using std::unordered_map;using std::unordered_set;using std::bitset;using std::pair;using std::set;using std::string;using std::vector;using std::sort;using ll=long long;using uint=unsigned int;using pii=pair<int,int>;using pll=pair<ll,ll>;using ull = unsigned long long;using ld=long double;template<typename T>void _(const char*s,T h){cerr<<s<<" = "<<h<<"\n";}template<typename T,typename...Ts>void _(const char*s,T h,Ts...t){int b=0;while(((b+=*s=='(')-=*s==')')!=0||*s!=',')cerr<<*s++;cerr<<" = "<<h<<",";_(s+1,t...);}// break continue pop_back 998244353
#define int ll
#define pii pll
#define f first
#define s second
#define pb emplace_back
#define forn(i,n) for(int i=0;i<(n);++i)
#define sqr(x) ((x)*(x))
struct init{init(){cin.tie(0);std::iostream::sync_with_stdio(0);cout<<std::fixed<<std::setprecision(10);cerr<<std::fixed<<std::setprecision(5);}~init(){
#ifdef LOCAL
#define dbg(...) _(#__VA_ARGS__,__VA_ARGS__)
cerr<<"Time elapsed: "<<(double)clock()/CLOCKS_PER_SEC<<"s.\n";
#else
#define dbg(...) 
#endif
}}init;template<typename T,typename U>void upx(T&x,U y){if(x<y)x=y;}template<typename T,typename U>void upn(T&x,U y){if(x>y)x=y;}
const double PI=3.1415926535897932384626433;
struct vc{
    double x,y;
};
double operator *(vc a,vc b){
    return a.x*b.x+a.y*b.y;
}
void operator +=(vc& a,vc b){
    a.x+=b.x;
    a.y+=b.y;
}
double get(vc v){
    return sqrtl(v.x*v.x+v.y*v.y);
}
const int N=100;
vc a[N];
int32_t main(){
    int n;
    cin>>n;
    forn(i,n){
        cin>>a[i].x>>a[i].y;
    }
    int IT=1e6;
    double ans=0;
    forn(z,IT){
        double ang=PI*2*z/IT;
        double x=sinl(ang);
        double y=cosl(ang);
        vc v={x,y};
        vc we={0,0};
        forn(i,n){
            if(a[i]*v>0){
                we+=a[i];
            }
        }
        // dbg(we.x,we.y,get(we));
        upx(ans,get(we));
    }
    cout<<ans<<'\n';


    return 0;
}


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

int main() {
  int n, k, q;
  cin >> n >> k >> q;
  vector<int> p(n, k - q);
  rep(i, q) {
    int a;
    cin >> a;
    p[a - 1]++;
  }

  rep(i, n) {
    if (p[i] > 0) {
      cout << "Yes" << endl;
    } else {
      cout << "No" << endl;
    }
  }

  return 0;
}

Measured memory_bytes: 3788
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>

using namespace std;

int main(){
	int n,m,a,b;
	int flag=0;
	int count[100001]={};
	cin >> n >> m;
	for(int i=0;i<m;i++){
		cin >> a >> b;
		count[a]+=1;
		count[b]+=1;
	}
	for(int i=1;i<=n;i++){
		if(count[i]%2==1){
			flag=1;
		}
	}
	if(flag==0){
		cout << "YES" <<endl;
	}else{
		cout << "NO" << endl;
	}
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define FIO "friend"
#define mset(a,b) memset(a,b,sizeof a)
#define mcpy(a,b) memcpy(a,b,sizeof b)
#define xx first
#define yy second
#define pb push_back
#define mp make_pair
#define pii pair<int,int> 
#define lb(x) ((x)&(-(x)))
#define dalao 1000000007
#define inf 0x3f3f3f3f
#define N 200010
#define M 2010
using namespace std;
typedef long long ll;
int n,a[N],b[N],fac[M<<2]={1},inv[M<<2],f[M<<1][M<<1];
inline void upd(int& a,int b){a=a+b>=dalao?a+b-dalao:a+b;}
inline int pw(int a,int b){int r=1;for(;b;b>>=1,a=1ll*a*a%dalao)b&1?r=1ll*r*a%dalao:0;return r;}
inline int C(int a,int b){return a<b?0:1ll*fac[a]*inv[b]%dalao*inv[a-b]%dalao;}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]),f[2000-a[i]][2000-b[i]]++;
	for(int i=1;i<=8000;i++)fac[i]=1ll*fac[i-1]*i%dalao;
	inv[8000]=pw(fac[8000],dalao-2);
	for(int i=7999;~i;i--)inv[i]=1ll*inv[i+1]*(i+1)%dalao;
	for(int i=0;i<=4000;i++)for(int j=0;j<=4000;j++)if(f[i][j])
		upd(f[i+1][j],f[i][j]),upd(f[i][j+1],f[i][j]);
	int ans=0;
	for(int i=1;i<=n;i++)upd(ans,f[2000+a[i]][2000+b[i]]),upd(ans,dalao-C((a[i]<<1)+(b[i]<<1),a[i]<<1));
	printf("%lld",500000004ll*ans%dalao);
	return 0;
}

Measured memory_bytes: 65024
import java.util.*;


public class Main{
	public static void main(String args[]){
		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n+1];
  		int count =0;
		a[0]= 0;
		
		
		for(int i=1;i<=n;i++){
			int b = sc.nextInt();
			a[i] = b;
		}
			Arrays.sort(a);
			
			
			for(int j=0;j<n;j++){
				    if(a[j] < a[j+1]){
						count++;
				    }
			}
			
		System.out.println(count);
	}
}

Measured memory_bytes: 22612
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <utility>
#include <tuple>
#include <map>
using namespace std;


int main() {
    int k, current = 7, total = 7, count = 1;
    cin >> k;
    current %= k;
    if (k % 2 == 0 or k % 5 == 0) {
        cout << -1;
    }
    else {
        while (total % k != 0) {
            count++;
            current *= 10;
            current %= k;
            total += current;
            total %= k;
        }
        cout << count;
    }
    return 0;
}

Measured memory_bytes: 3156
#include<stdio.h>

int main(void){
  
 int R; 
  
  scanf("%d", &R);
  
  if(R < 1200)
  {
  
    printf("ABC");
    
  }
  if(R > 1199 && R < 2800)
  {
  
    printf("ARC");
    
  }
   if(R > 2799)
  {
  
    printf("AGC");
    
  }
  
  
 return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < n; ++i)
typedef long long ll;
using namespace std;
const int INF = 1e9;

int n, m, q;
vector<int> a, b, c, d;
int ans;
void dfs(vector<int> A) {
    if (A.size() == n + 1) {
        int now = 0;
        rep(i, q) {
            if (A[b[i]] - A[a[i]] == c[i])
                now += d[i];
        }
        ans = max(ans, now);
        return;
    }

    A.push_back(A.back());
    while (A.back() <= m) {
        dfs(A);
        A.back()++;
    }
}

int main() {
    cin >> n >> m >> q;
    a = b = c = d = vector<int>(q);
    rep(i, q) cin >> a[i] >> b[i] >> c[i] >> d[i];

    dfs(vector<int>(1, 1));

    cout << ans << endl;

    return 0;
}

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

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

    int max = 0;
    for (int b = 1; b <= 100; ++b) {
        for (int p = 2; p <= 10; ++p) {
            const int v = std::pow(b, p);
            if (X < v) {
                break;
            }
            max = std::max(max, v);
        }
    }

    std::cout << max << std::endl;

    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;

using namespace std;

int main(int argc, char const* argv[])
{
    ll N,K,Q;
    cin >> N;
    cin >> K;
    cin >> Q;

    vector<ll> correct(N,0);
    vector<string> suviv(N);
    rep(i,Q){
        int ans;
        cin >> ans;
        correct[ans-1] += 1;
    }
    rep(i,N){
        if((correct[i] - Q + K) <= 0)
            suviv[i] = "No";
        else
            suviv[i] = "Yes";
    }
    rep(i,N){
        cout << suviv[i] << endl;
    }

    return 0;
}


Measured memory_bytes: 6912
S = input()
T = input()

# Sと同じ文字列分だけTを数えるのにTをlen関数を使って定義したいけど書き方がわからない #
# 解決策 「スライス機能」を使おう！
T = T[:len(S)]

if S == T :
    print("Yes")

else :
    print("No")

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

#define rep(i,n) for(long long i = 0; i < (long long)(n); i++)
#define repi(i,a,b) for(long long i = (long long)(a); i < (long long)(b); i++)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define mt make_tuple
#define mp make_pair
template<class T1, class T2> bool chmin(T1 &a, T2 b) { return b < a && (a = b, true); }
template<class T1, class T2> bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

using ll = long long; using vll = vector<ll>; using vvll = vector<vll>; using P = pair<ll, ll>;
using ld = long double;  using vld = vector<ld>; 

int main(void) {
    string s;
	rep(i,9)  cin >>s[i];
	
	cout<<s[0]<<s[4]<<s[8]<<endl;
	
    return 0;
}

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

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

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

const int MAX = 2 * 1e5 + 5;
const int INF = 1001001001;
const int MOD = 1e9 + 7;

vector<int> G[MAX];
vector<bool> used;
void dfs(int n) {
    used[n] = true;
    for (int next : G[n]) {
        if (!used[next]) dfs(next);
    }
}

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

    rep(i, N) {
        int K;
        cin >> K;

        rep(j, K) {
            int L;
            cin >> L;
            
            int lang = N + L - 1;
            G[i].push_back(lang);
            G[lang].push_back(i);
        }
    }

    used = vector<bool>(N + M, false);
    dfs(0);

    bool ans = true;
    rep(i, N) ans &= used[i];

    if (ans) puts("YES");
    else puts("NO");
}

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

using namespace std;
typedef long long ll;
const int maxn=1e4+7;

char mp[10][10];
int row[10],col[10];
int main() {
	int n,m,k,t;
	
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++){
		scanf("%s",mp[i]+1);
		//printf("%s",mp[i]);
	}
	int ans=0;
	for(int i=0;i<(1<<n);i++){
		for(int j=0;j<(1<<m);j++){
			int sum=0;
			for(int l=1;l<=n;l++){
				if((((i>>(l-1))&1))) continue;
				for(int p=1;p<=m;p++){
					if(((j>>(p-1))&1)) continue;
                    if(mp[l][p] == '#') sum++;
				}
			}
			if(sum == k) ans++;
			
		}
	}
	printf("%d\n",ans);
	
	
	return 0;
}


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

int main() {
    string S; cin >> S;
    int Q; scanf("%d", &Q);
    int nReverse = 0;
    vector<char> h1, h2;
    while (Q--) {
        int T; scanf("%d", &T);
        if (T == 1) {
            nReverse++;
        } else {
            int F; scanf("%d", &F);
            char C; scanf(" %c", &C);
            if (F == 1) {
                if (nReverse % 2 == 0) {
                    h1.push_back(C);
                } else {
                    h2.push_back(C);
                }
            } else {
                if (nReverse % 2 == 0) {
                    h2.push_back(C);
                } else {
                    h1.push_back(C);
                }
            }
        }
    }
    if (nReverse % 2 == 0) {
        for (int i = h1.size() - 1; i >= 0; --i) {
            printf("%c", h1[i]);
        }
        for (int i = 0; i < S.size(); ++i) {
            printf("%c", S[i]);
        }
        for (int i = 0; i < h2.size(); ++i) {
            printf("%c", h2[i]);
        }
        printf("\n");
    } else {
        for (int i = h2.size() - 1; i >= 0; --i) {
            printf("%c", h2[i]);
        }
        for (int i = S.size() - 1; i >= 0; --i) {
            printf("%c", S[i]);
        }
        for (int i = 0; i < h1.size(); ++i) {
            printf("%c", h1[i]);
        }
        printf("\n");
    }
    return 0;
}


Measured memory_bytes: 1024
# AGC031
import collections
mod = 10 ** 9 + 7
N = int(input())
S = list(input())
c = collections.Counter(S)
c = c.most_common()
ans = 1
##print(c)
for i in range(len(c)):
    ans *= (c[i][1]+1) % mod
ans -= 1
ans %= mod
print(ans)

Measured memory_bytes: 4340
#include <bits/stdc++.h>
using namespace std;
 
#define froop1(a,n) for(int i = a;i < n;i++)
#define froop2(a,n) for(int i = a;i > n;i--)
int main(){
	double N;
	cin >> N;
  N *= 2 * 3.14159265359;
  printf("%.3f\n",N);
return 0;
}

Measured memory_bytes: 3788
import sys

n, m = map(int, input().split())
ed = [[] for _ in range(n)]
v = [None] * n
for _ in range(m):
	l, r, d = map(int, input().split())
	ed[l-1].append([r-1, d])
	ed[r-1].append([l-1, -d])

visited = [False] * n

def dfs(start):
	global ed, v, visited
	s = [start]
	v[start] = 0
	while s:
		label = s.pop()
		if visited[label] == False:
			visited[label] = True
			for e in ed[label]:
				if v[e[0]] is None:
					v[e[0]] = v[label] + e[1]
					s.append(e[0])
				else:
					if v[e[0]] != v[label] + e[1]:
						print("No")
						sys.exit()
	return

for i in range(n):
	if v[i] is None:
		dfs(i)

print("Yes")

Measured memory_bytes: 105248
#include <bits/stdc++.h>
using namespace std;
int i,o,p;
int main () {
cin >> i>>o>>p;
if (i>p) {
	cout << "NO" << endl;
} else if ((i+o)<p) {
	cout << "NO"<<endl;
} else {
	cout <<"YES"<<endl;
}
}


Measured memory_bytes: 256
main :: IO ()
main = do
    n <- readLn
    print $ solve n

solve :: Int -> Int
solve n = solve' n (round $ sqrt $ fromIntegral n)

solve' :: Int -> Int -> Int
solve' n a
    | r == 0 = f a q
    | otherwise = solve' n (a - 1)
    where (q, r) = n `divMod` a

f :: Int -> Int -> Int
f a b = maximum $ map (length . show) [a, b]


Measured memory_bytes: 892
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define P pair<int,int>
#define ms(x) memset(x,0,sizeof(x));
#define forn(i,a,b) for(int i=(a);i<=(b);++i)
#define rev(i,a,b) for(int i=(a);i>=(b);--i)
#define sc(x) scanf("%d",&x)
#define bug(x) cerr<<#x<<":"<<(x)<<endl
using namespace std;
typedef long long ll;
const int M = 210000;
struct edge{
    int to,nx;
    int c,d;
}e[M];
struct node{
    node(int x):a(x){}
    int a,b,c;
    bool operator < (const node & v)const{
        return a<v.a;
    }
};
P operator+(const P & u,const P & v){
    return {u.first+v.first,u.second+v.second};
}
P operator-(const P & u,const P & v){
    return {u.first-v.first,u.second-v.second};
}
P operator*(int u,const P & v){
    return {v.first<<1,v.second<<1};
}
int h[M]={0};
int cnt=2;
const int m=20;
int f[m+1][M];
vector<node> g[M];
struct query{
    int u,v,x,y;
    int lca;
}q[M];
int n,Q;
int dis[M];
int dep[M];
void add(int u,int v,int c,int d){
    e[cnt].c = c;
    e[cnt].d = d;
    e[cnt].to = v;
    e[cnt].nx = h[u];
    h[u] = cnt++;
}
void dfs(int u,int fa,int ds,int depth){
    dis[u] = ds;
    f[0][u] = fa;
    dep[u] = depth;
    for(int i=h[u];i;i=e[i].nx){
        int t=e[i].to;
        if(t==fa) continue;
        dfs(t,u,ds+e[i].d,depth+1);
    }
}
void zen(){
    forn(i,1,m)
        forn(j,1,n)
            f[i][j] = f[i-1][f[i-1][j]];
}
int Lca(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    int k=dep[u]-dep[v];
    for(int i=m;i>-1;--i){
        if((1<<i)<=k){
            u=f[i][u];
            k-=(1<<i);
        }
    }
    if(u==v) return u;
    for(int i=m;i>-1;--i){
        if(f[i][u]!=f[i][v]){
            u=f[i][u];
            v=f[i][v];
        }
    }
    return f[0][u];
}
P co[M];
void fj(int u,int fa){
    sort(g[u].begin(),g[u].end());
    int len=g[u].size();
    forn(i,0,len-1){
        g[u][i].b=co[g[u][i].a].first;
        g[u][i].c=co[g[u][i].a].second;
    }
    for(int i=h[u];i;i=e[i].nx){
        if(e[i].to==fa) continue;
        ++co[e[i].c].first;
        co[e[i].c].second += e[i].d;
        fj(e[i].to,u);
        --co[e[i].c].first;
        co[e[i].c].second -= e[i].d;
    }
}
P get(vector<node> & v,int color){
    int lo=0,hi=v.size()-1;
    int mid=(lo+hi)>>1;
    while(lo<hi){
        if(v[mid].a<color) lo=mid+1;
        else hi=mid;
        mid=(lo+hi)>>1;
    }
    return {v[lo].b,v[lo].c};
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>Q;
    int a,b,c,d;
    forn(i,2,n){
        cin>>a>>b>>c>>d;
        add(a,b,c,d);
        add(b,a,c,d);
    }
    dfs(1,1,0,1);
    zen();
    forn(i,1,Q){
        cin>>q[i].x>>q[i].y>>q[i].u>>q[i].v;
        q[i].lca=Lca(q[i].u,q[i].v);
        g[q[i].u].push_back(node(q[i].x));
        g[q[i].v].push_back(node(q[i].x));
        g[q[i].lca].push_back(node(q[i].x));
    }
    fj(1,1);
    forn(i,1,Q){
        a=q[i].u;
        b=q[i].v;
        c=q[i].lca;
        int len=dis[a]+dis[b]-2*dis[c];
        P ret=get(g[a],q[i].x)+get(g[b],q[i].x)-2*get(g[c],q[i].x);
        len = len-ret.second+q[i].y*ret.first;
        cout<<len<<endl;
    }
    return 0;
}

Measured memory_bytes: 44728
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
import numpy as np
def bisearch(t):
  dp=np.full(k+1,False)
  dp[0]=True
  for i in range(n):
    if i==t:continue
    dp[a[i]:] = np.logical_or(dp[a[i]:], dp[:-a[i]]) 
  return any(dp[max(0,k-a[t]):k])
l,r=-1,n
while r-l>1:
  x=(l+r)//2
  if bisearch(x):
    r=x
  else:
    l=x
print(r)


Measured memory_bytes: 13208
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons;

void main()
{
    auto N = readln.chomp.to!int;
    auto K = readln.chomp.to!int;

    auto ret = 1;
    foreach (_; 0..N)
        ret = min(ret * 2, ret + K);
    writeln(ret);
}

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

int main() {
  int len;
  string str;
  int k;
  cin >> len >> str >> k;
  
  char c = str[k-1];
  for(int i=0; i<len; ++i) {
    cout << (str[i] == c ? c : '*');
  }
  cout << endl;
}


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

using namespace std;
typedef long long int ll;
typedef pair <ll,ll> P;
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define REPR(i, n) for(int i = n-1; i >= 0; i--)
#define PRINT(x) cout << x << endl

ll gcd(ll a, ll b) { return b ? gcd(b,a%b) : a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

ll MOD = 1000000007;


int main()
{
    ll N;
    cin >> N;
    map<ll, ll> m;
    REP(i, N) {
        ll a;
        cin >> a;
        m[a]++;
    }
    bool flag = m.size() == 1 && m[0] == N;
    flag |= m.size() == 2 && N % 3 == 0 && m[0] == N/3;
    ll sum = 0;
    bool flag2 = true;
    for(P t : m) {
        sum ^= t.first;
        flag2 &= t.second == N / 3;
    }
    flag |= m.size() == 3 && N % 3 == 0 && sum == 0 && flag2;
    if (flag) {
        PRINT("Yes");
    } else {
        PRINT("No");
    }
    return 0;
}


Measured memory_bytes: 5120
h,w=map(int,input().split())
s=['*'+'.'+'*'*w]+['*'+input()+'*' for i in range(h)]+['*'*(w+2)]
b=10**9
d=[[b]*(w+2)]+[[b]+[0]*w+[b] for _ in range(h)]+[[b]*(w+2)]
d[0][1]=0
for i in range(1,h+1):
  for j in range(1,w+1):
    d[i][j]=min(d[i-1][j]+(s[i][j]=='#')*(s[i-1][j]=='.'),d[i][j-1]+(s[i][j]=='#')*(s[i][j-1]=='.'))
print(d[h][w])

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
typedef long long ll;
#define repp(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
long long modpow(long long a,long long n,long long p)
{
    if(n==1)
    {
        return a%p;
    }
    if(n%2==1)
    {
        return a*modpow(a,n-1,p)%p;
    }
    long long t = modpow(a,n/2,p);
    return t*t%p;
}


int main()
{
    int n;
    cin>>n;
    if(n%2==1)
    {
        cout<<n/2+1<<endl;
    }
    else
    {
        cout<<n/2<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
#define SZ 666666
int n,m,x[SZ],y[SZ],gg[SZ];
bool S[555][555];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
		scanf("%d%d",x+i,y+i);
	for(int i=1;i<=n;++i)
	{
		bool*s=S[i];
		for(int j=1;j<=n;++j) s[j]=0; s[i]=1;
		for(int j=m;j>=1;--j)
		{
			if(s[x[j]]&&s[y[j]]) {gg[i]=1; goto out;}
			else if(s[x[j]]||s[y[j]])
				s[x[j]]=s[y[j]]=1;
		}
		out:;
	}
	int cnt=0;
	for(int i=1;i<=n;++i)
		for(int j=i+1;j<=n;++j)
			if(gg[i]||gg[j]);else
			{
				bool pp=1;
				for(int r=1;r<=n;++r)
					if(S[i][r]&&S[j][r]) pp=0;
				cnt+=pp;
			}
	printf("%d\n",cnt);
}


Measured memory_bytes: 4608
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
  string str;
  getline(cin, str);

  vector<int> count(26, 0);
  int64_t res = 1;

  for (size_t i = 0; i < str.size(); ++i) {
    res += i - count[str[i] - 'a'];
    count[str[i] - 'a'] += 1;
  }

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

Measured memory_bytes: 640
#define _USE_MATH_DEFINES
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <clocale>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i, s, n) for(int i = (s), i##_len=(n); i < i##_len; ++i)
#define FORS(i, s, n) for(int i = (s), i##_len=(n); i <= i##_len; ++i)
#define VFOR(i, s, n) for(int i = (s); i < (n); ++i)
#define VFORS(i, s, n) for(int i = (s); i <= (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) FORS(i, 0, n)
#define VREP(i, n) VFOR(i, 0, n)
#define VREPS(i, n) VFORS(i, 0, n)
#define RFOR(i, s, n) for(int i = (s), i##_len=(n); i >= i##_len; --i)
#define RFORS(i, s, n) for(int i = (s), i##_len=(n); i > i##_len; --i)
#define RREP(i, n) RFOR(i, n, 0)
#define RREPS(i, n) RFORS(i, n, 0)
#define ALL(v) (v).begin(), (v).end()
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v), greater<decltype(v[0])>())
#define SZ(x) ((int)(x).size())
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase(unique(ALL(v)), v.end())

using ll = long long;
using Pi_i = pair<int, int>;
using VB = vector<bool>;
using VC = vector<char>;
using VD = vector<double>;
using VI = vector<int>;
using VLL = vector<ll>;
using VS = vector<string>;
using VSH = vector<short>;

const int MOD = 1000000007;
const int INF = 1000000000;
const int NIL = -1;

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


int V; // 頂点数
VI d; //d[i] vからjまでのコスト  同じ点では0
vector<VI> G;
VI par;
vector<Pi_i> leaf;// -d, idx

int commonAncestor(int u, int v){
    if(u == v) return u;
    if(d[u] > d[v]) return commonAncestor(par[u], v);
    return commonAncestor(u, par[v]);
}

int distant(int u, int v){
    return d[u] + d[v] - 2 * d[commonAncestor(u, v)];
}

int main(){
    int u, v; cin >> V >> u >> v;
    --u; --v;
    d.resize(V, -1);
    par.resize(V, -1);
    G.resize(V);
    d[v] = 0;
    par[v] = NIL;
    REP(i, V-1){
        int a, b; cin >> a >> b; --a; --b;
        G[a].PB(b); G[b].PB(a);
    }
    queue<int> q;
    q.push(v);
    while(!q.empty()){
        int cur = q.front(); q.pop();
        int dist = d[cur];
        int cntchild = 0;
        for(auto next: G[cur]){
            if(d[next] != -1) continue;
            d[next] = dist + 1;
            par[next] = cur;
            q.push(next);
            ++cntchild;
        }
        if(!cntchild) leaf.PB(MP(-dist, cur));
    }
    SORT(leaf);
    int goal = NIL;
    for(auto& l: leaf){
        if(d[l.second] > distant(u, l.second)){
            goal = l.second; break;
        }
    }
    cout << d[goal] - 1 << "\n"; 
    return 0;
}


Measured memory_bytes: 7292
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(v) v.begin(),v.end()
#define mem(arr) memset(arr, 0, sizeof(arr))
#define ff first
#define ss second
#define int long long int
const int MOD = 1e9 + 7;
const int INF = 1e18;
const int N = 1e6 + 20;
vector<int> g[N];
vector<int> vis(N);
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc = 1;
    while(tc--){
        int a[3];
        cin >> a[0] >> a[1] >> a[2];
        swap(a[0], a[1]);
        swap(a[0], a[2]);
        cout << a[0] << ' ' << a[1] << ' ' << a[2] << '\n';
    }
}

Measured memory_bytes: 31488
#include<stdio.h>
long long ans,n,m;
main()
{
	scanf("%lld%lld",&n,&m);
	if(m==0) printf("%lld\n",n*n);
	else
	{
		for(int i=m+1;i<=n;i++) ans+=(n/i)*(i-m)+(n%i-m+1)*(n%i>=m?1:0);
		printf("%lld\n",ans);
	}
	return 0;
}

Measured memory_bytes: 128
#include<stdio.h>
#include<string.h>
int MIN(int a,int b){return a<b?a:b;}
int main(){
  int n,i,l;
  char s[100010];
  scanf("%s %d",s,&n);
  for(i=0;s[i];i++){
    if(s[i]=='a')continue;
    if(n>'z'-s[i]){
      n-='z'-s[i]+1;
      s[i]='a';
    }
  }
  l=strlen(s)-1;
  s[l]=(s[l]-'a'+n)%26+'a';
  printf("%s\n",s);
  return 0;
}
  


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

typedef long long int int64;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))

void run(void){
  int n,y;
  scanf("%d%d",&n,&y);
  int *x=(int *)calloc(n,sizeof(int));
  int i,j;
  for(i=0;i<n;i++) scanf("%d",x+i);
  int64 *xsum=(int64 *)calloc(n+1,sizeof(int64));
  for(i=1;i<=n;i++) xsum[i]=xsum[i-1]+x[i-1];
  int64 ans=1000000000LL*5*200000+1000000000LL*400000;;
  for(i=1;i<=n;i++){
    int64 sum=(int64)y*(n+i);
    int k=1;
    for(j=n;j>0;j-=i,k++){
      sum+=(k==1?5:1+2*k)*(xsum[j]-xsum[MAX(0,j-i)]);
      if(sum>ans) break;
    }
    ans=MIN(ans,sum);
  }
  printf("%lld\n",ans);
}

int main(void){
  run();
  return 0;
}


Measured memory_bytes: 2560
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <numeric>

using namespace std;

int main(){

  int a, b;
  cin >> a >> b;

  if ((a + b) >= 10){
    cout << "error" << endl;
  }
  else {
    cout << a + b << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <unistd.h>
#include <sys/stat.h>
#include <stdio.h>
#include <vector>
#include <cmath>
#include <random>
#include <string.h>      //文字列の代入に使う
#include <bits/stdc++.h> //piの利用で必要(M_PI)
#include <algorithm>

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

int main()
{

    int K, sum = 0;
    std::cin >> K;
    for (int i = 1; i <= K; i++)
    {
        for (int j = 1; j <= K; j++)
        {
            for (int k = 1; k <= K; k++)
            {
                //std::cout << gcd(gcd(i, j), k) << std::endl;
                sum += gcd(gcd(i, j), k);
            }
        }
    }

    std::cout << sum << std::endl;
    return 0;
}

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

using namespace std;

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

Measured memory_bytes: 1024
def is_unique(seq):
    seen = []
    unique_list = [x for x in seq if x not in seen and not seen.append(x)]
    return len(seq) == len(unique_list)

n = int(input())
tango = []
for i in range(n):
    tango.append(list(input()))
    
rule1 = True
rule2 = True

for i in range(n-1):
    if tango[i][len(tango[i])-1] != tango[i+1][0]:
        rule1 = False

if not is_unique(tango):
    rule2 = False
    
if rule1 and rule2:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3064
main :: IO ()
main = do
    str <- getLine
    let inputs = [read word :: Int | word <- words str]
    putStrLn $ unwords $ map (show . (\x -> x inputs)) [area, circum]

area :: [Int] -> Int
area (a:b:_) = a * b

circum :: [Int] -> Int
circum (a:b:_) = 2 * (a + b)

Measured memory_bytes: 3480
#include <iostream>
#include <cstdio>
#include <stack>

using namespace std;

int main()
{
    int n,w;
    cin >> n >> w;
    long long int f[n+1][w+1];
    long long int m[n+1];
    long long int v[n+1];
    for ( int i = 1; i <= n ; i ++ )
        cin >> m[i] >> v[i];
    for ( int i = 0 ; i <= n ; i++ )
        f[i][0] = 0;
    for ( int i = 1; i <= w; i++ )
        f[0][i] = 0;
    for ( int i = 1; i <= n; i++ )
    {
        for ( int j = 1; j <= w; j++ )
        {
            if ( m[i] > j )
            {
                f[i][j] = f[i-1][j];
            }
            else
                f[i][j] = max(f[i-1][j],f[i-1][j-m[i]] + v[i]);
        }
    }
    cout << f[n][w]<<endl;
    return 0;
}


Measured memory_bytes: 79104
import java.io.*;

public class Main {  
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Main m = new Main();
        String line = br.readLine();
        int[] num = m.splitIntChange(line);
        int area = num[0]*num[1];
        int cir = (num[0]+num[1])*2;
        System.out.println(area+" "+cir);
         
    }
     
    public int[] splitIntChange(String str){
        String[] str_ = str.split(" ");
        int strlen = str_.length;
        int[] numarray = new int[strlen];
         
        for(int i = 0;i < strlen;i++){
            numarray[i] = Integer.parseInt(str_[i]); 
        }
         
        return numarray;
    }
}

Measured memory_bytes: 24120
n = int(input())
a = sorted(list(map(int, input().split())),reverse=True)
i = 0
cnt = 1
ans = a[0]
a.pop(0)
while i < n-1 or cnt < n - 1:
    for j in range(2):
        if cnt == n - 1:
            break
        cnt += 1
        ans += a[i]
        #print(cnt,ans)
    i += 1
print(ans)

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

int main(){
    int a, b;
    cin >> a >> b;
    if(a == 1)  a = 14;
    if(b == 1)  b = 14;

    if(a > b)   cout << "Alice" << endl;
    if(a < b)   cout << "Bob" << endl;
    if(a == b)  cout << "Draw" << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define endl        '\n'
#define pi          2*acos(0.0)
#define pb(a)       push_back(a)
#define db          double
#define ld          long double
#define ll          long long
#define ull         unsigned long long
#define mod         1000000007
#define inf         1000000000000000001
#define sqr(x)      (x) * (x)
#define gcd(a, b)   __gcd(a, b)
#define lcm(a, b)   ((a/gcd(a,b)) * b)
#define debug(x) 	cerr << #x << " = " << (x) <<endl
#define all(x)      (x).begin(), (x).end()
#define unsyncIO    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)


using namespace std;

int main()
{
	unsyncIO;
    //freopen("/home/taalpatar_shepai/Documents/my_codes/out.txt", "w", stdout);
    string s;
    vector<int> v (26);
    cin>>s;
    for (int i = 0; i < s.length(); i++) {
        int temp;
        temp = count(all(s), s[i]);
        v[s[i] - 'a'] = temp;
    }
    bool check = false;
    for (int i = 0; i < v.size(); i++) {
        if(v[i] != 0) {
            if(v[i] % 2 != 0) {
                check = true;
                break;
            }
        }
    }
    if(!check)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3524
use proconio::input;
use std::cmp;

fn main() {
    input! {
        n: usize,
        k: usize,
        ranges: [(usize, usize); k],
    }

    let mut dp = vec![0isize; n + 1];
    let mo = 998244353;
    dp[0] = 1;
    dp[1] = -1;
    for i in 0..n {
        for &range in &ranges {
            if i + range.0 > n - 1 {
                continue;
            }
            let li = i + range.0;
            let ri = cmp::min(n - 1, i + range.1);
            dp[li] += dp[i];
            dp[ri + 1] -= dp[i];
            dp[li] %= mo;
            dp[ri + 1] = (dp[ri+1] + mo) % mo;
        }
        dp[i+1] = (dp[i+1] + dp[i] + mo) % mo;
        /*
        print!("{}, dp : ", i);
        for i in 0..n {
            print!("{} ", dp[i]);
        }
        println!();
        */
    }
    /* 
    for i in 0..n {
        println!("dp[{}] : {}", i, dp[i]);
    }
    */

    println!("{}", dp[n - 1]);
}


Measured memory_bytes: 3644
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
char s[10][N];
int a[10],sum[10],num[10];
int main(){
	int n,m,s1,ans=1e9,K;scanf("%d%d%d",&n,&m,&K),s1=1<<(n-1);
	for(int i=0;i<n;i++)scanf("%s",s[i]);
	for(int i=0;i<s1;i++){
		int w=0,w1=0;for(int j=0;j<n;j++){a[j]=w;if(i&(1<<j))w++;}
		bool fl,fl1;memset(sum,0,sizeof(sum));
		for(int k=0;k<m;k++){
			memset(num,0,sizeof(num));
			for(int j=0;j<n;j++)num[a[j]]+=s[j][k]=='1';
			fl=0,fl1=0;
			for(int j=0;j<=w;j++){
				if((sum[j]+=num[j])>K){fl=1;}
				if(num[j]>K){fl1=1;break;}
			}
			if(fl1)break;
			if(fl){w1++;for(int j=0;j<=w;j++)sum[j]=num[j];}
		}
		if(fl1)continue;
		ans=min(ans,w+w1);
	}
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define repz(i, z, n) for (decltype(n) i = (z); i < (n); i++)
#define rep(i, n) for (decltype(n) i = 0; i < (n); i++)

#define REPZ(i, z, n) for (decltype(n) i = (z); i <= (n); i++)
#define REP(i, n) for (decltype(n) i = 0; i <= (n); i++)
#define ALL(v) v.begin(), v.end()
#define SIZE(v) ((ll)(v).size())
#define MAX(v) (*max_element(ALL(v)))
#define MIN(v) (*min_element(ALL(v)))
#define INF 1000000000000  // 1E+12

// 略
#define PB push_back
#define F first
#define S second
#define MP make_pair
#define READ cin >>
#define PRINT cout <<
#define PYES cout << "YES" << endl
#define pyes cout << "Yes" << endl
#define POK cout << "OK" << endl
#define PNO cout << "NO" << endl
#define pno cout << "No" << endl
#define PNG cout << "NG" << endl
#define ret return 0

using namespace std;

// デバッグ用
void debug_out() { cout << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cout << H << " ";
  debug_out(T...);
}

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 (a > b) {
    a = b;
    return true;
  }
  return false;
}

#ifdef _DEBUG
#define debug(...) debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

// typedef
typedef long long ll;
typedef unsigned long long ul;
typedef long double ld;
typedef pair<ll, ll> pl;

// const
// 円周率
const ld pi = acos(-1);
// mod用
// 1E+9 +7
const ll mod = (int)1e+9 + 7;
// 1s間で可能なループ回数2E+8回
// int        最大値2147483647         〜2E+9
// long long  最大値9223372036854775807〜9E+18
// 総和accumulate
// 単純リストvector<type> push_back
// 連想配列map<key,value> insert,
// 集合set<type>
// pair キーとバリューを格納 firstとsecondでアクセス
// 小数点指定 cout << fixed << setprecision(15) << endl;
// to_string<->stoi
// stoll(longlong)
// stod(double)
// deep copy v1->v2 copy(v1.begin(), v1.end(), back_inserter(v2) );
// 大文字65-90(-32)
// 小文字97-122(+32)
//  priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>>
//  ba;
signed main() {
  // faster
  // C言語流の入出力は使用できない
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n;
  cin >> n;
  vector<ld> p(n);
  vector<vector<ld>> dp(n, vector<ld>(n + 1, 0e+0));
  rep(i, n) { cin >> p[i]; }
  dp[0][0] = 1 - p[0];
  dp[0][1] = p[0];
  repz(i, 1, n) {
    repz(j, 0, n + 1) {
      if (j > 0)
        dp[i][j] = dp[i - 1][j - 1] * p[i] + dp[i - 1][j] * (1 - p[i]);
      else
        dp[i][j] = dp[i - 1][j] * (1 - p[i]);
    }
  }
  ld res = 0;
  repz(i, n / 2 + 1, n + 1) {
    res += dp[n - 1][i];
  }
  cout << fixed << setprecision(15) << res << endl;
  ret;
}


Measured memory_bytes: 144368
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stdbool.h>
#include<time.h>
#include<math.h>
#include<assert.h>
#define inf 1072114514
#define llinf 4154118101919364364
#define mod 1000000007
#define pi 3.1415926535897932384
int max(int a,int b){if(a>b){return a;}return b;}
int min(int a,int b){if(a<b){return a;}return b;}
int zt(int a,int b){return max(a,b)-min(a,b);}
int gcd(int a,int b){int c;while(b!=0){c=a%b;a=b;b=c;}return a;}
int lcm(int a,int b){int c=gcd(a,b);a/=c;return a*b;}
int nCr(int a,int b){int i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
int nHr(int a,int b){return nCr(a+b-1,b);}
int fact(int a){int i,r=1;for(i=1;i<=a;i++){r*=i;}return r;}
int dsum(int x){int r=0;while(x){r+=(x%10);x/=10;}return r;}
int dsumb(int x,int b){int r=0;while(x){r+=(x%b);x/=b;}return r;}
int sankaku(int x){return ((1+x)*x)/2;}
void swap(int *a,int *b){int c;c=(*a);(*a)=(*b);(*b)=c;}
//小さい順
int compareInt(const void* a, const void* b){int aNum = *(int*)a;int bNum = *(int*)b;return aNum - bNum;}

long long _gcd(long long a,long long b){
    long long c;
    while(b!=0){c=a%b;a=b;b=c;}
    return a;
    
}
long long _lcm(long long a,long long b){long long c=_gcd(a,b);a/=c;return a*b;}

int main(){
    int N;
    int ans=0;
    scanf("%d",&N);
    int a[N+3];
    a[0]=0;
    a[N+1]=0;a[N+2]=0;
    for(int i=1;i<N+1;i++){
        scanf("%d",&a[i]);
    }
    for(int i=0;i<=N;i++){
        ans+=abs(a[i]-a[i+1]);
    }
    for(int i=1;i<=N;i++){
        int sum=0;
        sum=ans+abs(a[i+1]-a[i-1])-(abs(a[i]-a[i-1])+abs(a[i]-a[i+1]));
        printf("%d\n",sum);
    }
    return 0;
}




Measured memory_bytes: 1536
#include<iostream>
#include<cmath>
#include<unordered_map>
#include<math.h>
#include<vector>
#include<queue>
#include<set>
#include<algorithm>
#include<iomanip>
#include<string>
#include<map>
#define PI 3.14159265
#define mod 998244353    
using namespace std;

 

void func(){
    long long n , w ;
    cin >> n >> w ;
    int val[n] , wt[n];
    vector<vector<long long>> dp(n + 1, vector<long long> (w + 1));

    for(int i = 0 ; i < n ; ++i){
      cin >> wt[i] >> val[i];
    }

    for(int i = 0 ; i <= n ; ++i){
        for(int j = 0; j <= w ; ++j){
            if(i == 0 || j == 0){
                dp[i][j] = 0;
            }
            else if(wt[i - 1] > j){
              dp[i][j] = dp[i - 1][j];
            }
            else{
              dp[i][j] = max(dp[i - 1][j] , val[i - 1] + dp[i - 1][j - wt[i - 1]]);
            }
        }
    }
     cout << dp[n][w] << "\n";
}
int main(){
    int t = 1 , cnt = 0 ;
  // cin >> t;
    
    while(t--){
        
        func();
    }
}

Measured memory_bytes: 80256
n,m = list(map(int,input().split()))
a = list(map(int,input().split()))
a.sort(reverse=True)

if n >= m:
    print(0)
    exit()

b = []
for i in range(m-1):
    b.append(abs(a[i+1]-a[i]))

b.sort()
print(sum(b[:m-n]))

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

struct UnionFind {
  vector<int> par; //par[i]:iの親の番号

  //最初は全てが根であるとする。-1のときに根である。
  UnionFind(int N) : par(N, -1){}

  // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
  int root(int x) {
    if(par[x] < 0) return x;
    else return par[x] = root(par[x]);
  }

  //xとyが同じ集合に属するか
  bool issame(int x, int y) {
    return root(x) == root(y);
  }

  void merge(int x, int y) {
    x = root(x); y = root(y);
    if(x == y) return;
    if(par[x] > par[y]) swap(x,y);
    par[x] += par[y];
    par[y] = x;
  }

  int size(int x) {
    return -par[root(x)];
  }
};

int deg[100005];
vector<int> to[100005];

int main() {
  int n, m, k;
  cin >> n >> m >> k;
  UnionFind uf(n);
  rep(i,m){
    int a, b;
    cin >> a >> b;
    a--; b--;
    deg[a]++;
    deg[b]++;
    uf.merge(a, b);
  }
  rep(i,k){
    int a, b;
    cin >> a >> b;
    a--; b--;
    to[a].push_back(b);
    to[b].push_back(a);
  }
  rep(i,n) {
    int ans = uf.size(i) - 1 - deg[i];
    for(int u : to[i]) {
      if(uf.issame(i,u)) ans--;
    }
    printf("%d%c", ans, i == n - 1 ? '\n' : ' ');
  }
  return 0;
}


Measured memory_bytes: 6784
// #include<iostream>
// #include<vector>
// #include<algorithm>
// #include<map>
// #include<cstring>
// #include<math.h>
// #include<bitset>
// #include<queue>
// #include<set>
// #include<iomanip>
// #include<math.h>
// #include<assert.h>
// #include<string>
// #include<cstdlib>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll INF = 1LL << 40;
const double INFD = 1e100;
const ll mod = 1000000007;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
// ----------------------------------------------------------------------------
  int main(){
    int A,B,C;
    cin >> A >> B >> C;
    if(A<=C && C<=B){
      cout << "Yes" << endl;
    }else{
      cout << "No" << endl;
    }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
int main()
{
   ll a,b;
    scanf("%lld%lld",&a,&b);
    if(a>b)
        swap(a,b);
    if(a==1&&b==1)
        cout<<"1"<<endl;
    else if(a==1)
        cout<<b-2<<endl;
    else if(a==2)
        cout<<"0"<<endl;
    else
        cout<<a*b-2*a-2*b+4<<endl;

    return 0;

}


Measured memory_bytes: 256