akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
#define INF 1<<50LL
#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define RFOR(i,a,b) for(long long i = (b-1);i>=a;i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
typedef long long ll;
typedef pair<ll,ll> P;

struct Edge{
  int x,y,cost;
};

struct Node{
  int x,y,id;
};

bool cmpx(Node& a,Node& b){
  return a.x < b.x;
}

bool cmpy(Node& a,Node& b){
  return a.y < b.y;
}

bool cmpc(Edge& a,Edge& b){
  return a.cost < b.cost;
}

vector <Edge>edge;  
vector <Node>node;

const int MAXN = 100100;
int tree[MAXN];
vector <int> child;
ll ans = 0;

int root(int i){
  if(i == tree[i]){
    for(int j = 0; j < child.size(); j++)
      tree[child[j]] = i;
    child.clear(); 
    return i;                   
  }
  else{
    child.push_back(i);
    return i = root(tree[i]);
  }
}

int unit(int x,int y){
  x = root(x);
  y = root(y);
  tree[max(x,y)] = min(x,y);     
}

bool isUnit(int x,int y){
  return root(x) == root(y);
}
  

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

  int n;
  cin >> n;

  REP(i,n){
    int x,y;
    cin >> x >> y;
    node.push_back({x,y,i});
  }
  
  sort(node.begin(),node.end(),cmpx);
  REP(i,n-1){
    edge.push_back({node[i].id,node[i+1].id,abs(node[i+1].x-node[i].x)});
  }
  
  sort(node.begin(),node.end(),cmpy);
  REP(i,n-1){
    edge.push_back({node[i].id,node[i+1].id,abs(node[i+1].y-node[i].y)});
  }
  
  sort(edge.begin(),edge.end(),cmpc);
  
/*  REP(i,edge.size()){
    cout << edge[i].x << " " << edge[i].y << " " << edge[i].cost << endl;
  }*/
  
  REP(i,n) tree[i] = i;
  
  REP(i,edge.size()){
    if(isUnit(edge[i].x,edge[i].y)) continue;
    unit(edge[i].x,edge[i].y);
    ans += edge[i].cost;
  }
  
  cout << ans << endl;

  return 0;
}


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

int main() {
  string a, b;
  cin >> a >> b;

  int i = 0;
  while (i < a.size()) {
    cout << a.at(i);
    if (i < b.size()) {
      cout << b.at(i);
    }
    i ++;
  }
  cout << endl;
}


Measured memory_bytes: 256
//include
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath> 
#include <iomanip>
#include <math.h>
#include <utility>
#include <functional>
#include <cstdlib>
//using
using namespace std;
using vl = vector <long long>;
using vs = vector <string>;
using vc = vector <char>;
using ll= long long;
using vvl = vector<vector<ll> >;
//vector<vector<char> > hyou(N, vector<char>(N));
using vd = vector <double>;
//define
//#define int long long
#define rep(i,n) for(int i=0; i<n; i++)
#define print(n) cout<<n<<endl;
#define sortp(d) sort(d.begin(),d.end()) //1234
#define sortm(d) sort(d.rbegin(),d.rend()) //4321
//素数判定　O(√A) 
bool is_prime(int x){
 if(x<=1) return false;
 for(int i=2;i*i<=x;i++)
 if(x%i==0) return false;
 return true;
 }
/*順列生成
do {
  // 順列に対する処理
} while (next_permutation(配列変数.begin(), 配列変数.end()));*/

//絶対値　abs()
//文字→数字　'0' アルファベット→数字　'a'

//グローバル変数宣言
 ll p=0,q=0,r=0;

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

	bool app[26];
	for (int i = 0; i < 26; ++i) {
		app[i] = false;
	}
	for (int i = 0; i < S.size(); ++i) {
		app[S[i] - 'a'] = true;
	}
	for (int i = 0; i < 26; ++i) {
		if (app[i]==false) {
			printf("%c\n", (char)(i + 'a'));
			return 0;
		}
	}
	puts("None");
	return 0;
}


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

int main()
{
    int N, M;
    cin >> N >> M;
    vector<pair<int, int>> sv;
    for(int i = 0;i < N;i++){
        int S, V;
        cin >> S >> V;
        sv.emplace_back(V, S);
    }
    sort(sv.begin(), sv.end());
    vector<int> C(M);
    for(int i = 0;i < M;i++){
        cin >> C[i];
    }
    sort(C.begin(), C.end());
    int lb = 0, ub = min(N, M) + 1;
    while(ub - lb > 1){
        int m = (lb + ub) / 2;
        int it = M - m;
        for(int i = 0;i < N && it < M;i++){
            it += sv[i].second <= C[it];
        }
        (it < M ? ub : lb) = m;
    }
    cout << lb << endl;
    return 0;
}



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

void solve(){
  int n,d;
  cin >> n >> d;
  double x[15][15];
  rep(i,n){
    rep(j,d){
      cin >> x[i][j];
    } 
  }
  int count = 0;
  for(int i=0; i<n; i++){
    for(int k=0; k<n; k++){
    double sum = 0;
    rep(j,d){
      sum += pow((x[k][j] - x[i][j]), 2); 
    }
    if(sum == pow((int)sqrt(sum),2) && i!=k){
      count++; 
    }
    }
  }
  cout << count/2 << endl;
}

int main(){
  solve();
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <regex>
#include <numeric>
using namespace std;

/*--- Macro ---*/
#define rep(i, n) for(int i=0; i<(int)n; i++)
#define rep1(i, n) for(int i=1; i<(int)n; i++)
#define mp make_pair
#define pb push_back
#define all(a) a.begin(), a.end()

/*---  Type ---*/
typedef long long ll;

/*--- Constants ---*/
template <typename T> const T INF = numeric_limits<T>::max() / 10;
const int MOD = (int)1e9 + 7;

// Floating
const double EPS = 1e-11;
#define EQ0(x) (abs(x) < EPS)
#define EQ(x, y) (abs(a-b) < EPS)

// Util
int max(int a, int b, int c) {return max(a, max(b, c));}
int min(int a, int b, int c) {return min(a, min(b, c));}
ll max(ll x, ll y) {return x > y ? x : y;}
ll min(ll x, ll y) {return x < y ? x : y;}
ll max(ll a, ll b, ll c) {return max(a, max(b, c));}
ll min(ll a, ll b, ll c) {return min(a, min(b, c));}

// -------------------------------------------------------------------------------------



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

  vector<int> v;
  int base = pow(100, d), cnt = 1;
  while(v.size() < n) {
    if(cnt % 100 != 0) {
      v.pb(base * cnt);
    }
    cnt++;
  }

  cout << v[n-1] << endl;

  return 0;
}

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

const long long N = 200001;
const long long K = 201;
long long n,k;
long long arr[N];
long long matrix[N][K];


long long checkmin(long long i){
  long long res = matrix[i][0];
  for(long long j = 0; j < k; j++){
    if(matrix[i][j] >= 0){
      res = min(res,matrix[i][j]);
    }
  }
  return res;
}


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

  for(long long i = 0; i < n; i++){
    cin >> arr[i];
  }

  for(long long r = 0; r < k; r++){
    for(long long f = 0; f < n; f++){
      if(r > n-f-2) matrix[f][r] = -1;
    }
    matrix[n-1][r] = 0;
    if(n-r-2>0){
      matrix[n-r-2][r] = abs(arr[n-r-2]-arr[n-1]);
    }

  }


  for(long long j = n-2; j >= 0; j--){
    for(long long h = 0; h < k; h++){
      if(h < n-j-1){
        matrix[j][h] = abs(arr[j] - arr[j+h+1]) + checkmin(j+h+1);
      }
    }
  }

  long long res = matrix[0][0];
  long long maximo = -1;
  for(long long a = 0; a < k; a++){
    res = min(res,matrix[0][a]);
    maximo = max(maximo,matrix[0][a]);
  }
  if(maximo == -1) res = 0;
  else if (res == -1){
    res = maximo;
    for(long long a = 0; a < k; a++){
      if(matrix[0][a] != -1){
        res = min(res,matrix[0][a]);
      }
    }
  }
  cout << res;
}


Measured memory_bytes: 160000
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
  private static class FastScanner {
    private BufferedReader reader = null;
    private StringTokenizer tokenizer = null;

    public FastScanner(InputStream in) {
      reader = new BufferedReader(new InputStreamReader(in));
      tokenizer = null;
    }

    public String next() {
      if (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          tokenizer = new StringTokenizer(reader.readLine());
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }
      return tokenizer.nextToken();
    }

    public String nextLine() {
      if (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          return reader.readLine();
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }

      return tokenizer.nextToken("\n");
    }

    public long nextLong() {
      return Long.parseLong(next());
    }

    public int nextInt() {
      return Integer.parseInt(next());
    }

    public double nextDouble() {
      return Double.parseDouble(next());
    }

    public int[] nextIntArray(int n) {
      int[] a = new int[n];
      for (int i = 0; i < n; i++)
        a[i] = nextInt();
      return a;
    }

    public long[] nextLongArray(int n) {
      long[] a = new long[n];
      for (int i = 0; i < n; i++)
        a[i] = nextLong();
      return a;
    }
  }

  public static void main(String[] args) {
    FastScanner sc = new FastScanner(System.in);
    int n = sc.nextInt();
    long[] a = sc.nextLongArray(n);
    Arrays.sort(a);
    PriorityQueue<long[]> pq = new PriorityQueue<>((long[] x, long[] y) -> {
      long minX = Math.min(x[0], x[1]);
      long maxX = Math.max(x[0], x[1]);
      long minY = Math.min(y[0], y[1]);
      long maxY = Math.max(y[0], y[1]);
      if (minX != minY) return minY > minX ? 1 : -1;
      return maxY > maxX ? 1 : -1;
    });
    pq.add(new long[] {a[n - 1], a[n - 2]});
    pq.add(new long[] {a[n - 1], a[n - 2]});
    long result = a[n - 1];
    for (int i = n - 3; i >= 0; i--) {
      long[] span = pq.poll();
      result += Math.min(span[0], span[1]);
      pq.add(new long[] {span[0], a[i]});
      pq.add(new long[] {span[1], a[i]});
    }
    System.out.println(result);
  }
}

Measured memory_bytes: 67956
#include <bits/stdc++.h>
using namespace std;
int main(){
    long long n,x,t;
    cin>>n>>x>>t;
    long long ans=n/x;
    if(n%x==0){
        cout<<ans*t<<endl;
    }
    else{
        cout<<(ans+1)*t<<endl;
    }
    return 0;
}


Measured memory_bytes: 3632
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int K = scan.nextInt();
		int S = scan.nextInt();
		
		int count = 0;
		
		for (int X = 0; X <= K; X++) {
			for (int Y = 0; Y <= K; Y++) {
				if (S - X - Y >= 0 && S - X - Y <= K) {
					count++;
				}
			}
		}
		
		System.out.print(count);
		
	}

}

Measured memory_bytes: 21712
from sys import setrecursionlimit
from heapq import heappush, heappop

max2 = lambda x,y: x if x > y else y

setrecursionlimit(1000000)


N = int(input())
A = [-1]+[int(input())-1 for _ in range(N-1)]

depth = [0]*N
wins = [0]*N

for a in A[1:]:
    wins[a] += 1

q = [(0,i) for i,w in enumerate(wins) if w == 0]

while q:
    w,v = heappop(q)
    if v == 0:
        continue
    u = A[v]
    wins[u] -= 1
    depth[u] = max2(depth[u],depth[v])+1
    if wins[u] == 0:
        heappush(q,(depth[u], u))

print(depth[0])

Measured memory_bytes: 91724
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    A = [NI() for _ in range(N)]
    B = copy.copy(A)
    B.sort()

    ans = 0
    for i in range(N):

        p = bisect.bisect_left(B,A[i])
        ans += (i - p) % 2
    print(ans//2)

if __name__ == '__main__':
    main()

Measured memory_bytes: 47704
using System;
using System.Collections.Generic;
using System.Linq;

namespace abc051

{
    public class Program
    {
        public static void Main(string[] args)
        {
            string[] str = Console.ReadLine().Split(',');
            string separate = " ";
            string outStr = string.Empty;

            for (int i = 0; i < str.Length; i++)
            {
                outStr += str[i] + separate;
            }

            outStr = outStr.Substring(0, outStr.Length - 1);

            Console.WriteLine(outStr);
        }
    }
}

Measured memory_bytes: 2776
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
#define rep(i,n) for (ll i=0;i<n;++i)
#define rep2(i,a,b) for (ll i=a;i<b;++i)
const ll MOD=1e9+7;
const ll INF=1e9;
const ll IINF=1e18;
const double EPS=1e-8;
const double pi=acos(-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(){
    ll N;
    cin >> N;
    vector<Pll> a(N+1);
    rep(i,N){
        ll b;
        cin >> b;
        a[i]=Pll(b,i);
    }
    a[N]=Pll(0,0);
    sort(a.begin(),a.end());
    reverse(a.begin(),a.end());
    vector<ll> ans(N);
    ll pre=a[0].second;
    rep(i,N){
        if (a[i].first==a[i+1].first) continue;
        ll x=a[i].first-a[i+1].first;
        chmin(pre,a[i].second);
        ans[pre]+=(i+1)*x;
    }
    rep(i,N) cout << ans[i] << endl;
}

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

#define what_is(x)    cerr<<#x<<" is "<<x<<"\n";
#define rep(i,n)      for(int i=0; i < (n); ++i)
#define pb            push_back
#define mp            make_pair
#define int           long long
#define fr            first
#define sc            second
#define vc            vector
#define all(x)        (x).begin(),(x).end()
#define rall(x)       (x).rbegin(),(x).rend()
#define sz(x)         (x).size()
#define M             1e9+7;
#define MM            998244353
#define PI            3.14159265358979

typedef long double ld;
typedef pair <int,int> pii;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mii;

int n,ans; string str;
void CountTriangles(vi A){  
  
    int n=A.size(); 
  
    sort(A.begin(), A.end());  
  
    int count = 0; 
      
    for( int i = n-1; i >= 1; i--){ 
        int l = 0, r = i-1; 
        while( l < r){ 
            if( A[l] + A[r] > A[i]){ 
                count += r - l ;  
                r--;   
            } 
            else 
                l++;   
        } 
    } 
    cout<<count;
} 
int solve(){
    cin>>n;
    vi v;
    rep(i,n){
        int a; cin>>a;
        v.pb(a);
    }
    CountTriangles(v);
    return 0;
}

signed main() {
    ios::sync_with_stdio(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}

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

#define ALL(v) (v).begin(),(v).end()

using namespace std ;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;




int main()
{
  int x, y ;
  cin >> x >> y ;
  
  if(x==4 || x==6 || x==9 || x==11){
    x = 100 ;
  }
  else if(x==2){
    x = 1000 ;
  }
  else{
    x = 10000;
  }
  if(y==4 || y==6 || y==9 || y==11){
    y = 100 ;
  }
  else if(y==2){
    y = 1000 ;
  }
  else{
    y = 10000 ;
  }
  
  if(x==y){
    cout <<"Yes"<<endl ;
  }
  else{
    cout <<"No"<<endl ;
  }
  
    return 0 ;
}

/*　吾輩はやれば出来る子である。 
　　　　∩∩ 
　　　（´･ω･） 
　　 ＿|　⊃／(＿＿_ 
　／　└-(＿＿＿_／ 
　￣￣￣￣￣￣￣ 
　やる気はまだない 

　　 ⊂⌒／ヽ-、＿_ 
　／⊂_/＿＿＿＿ ／ 
　￣￣￣￣￣￣￣　　*/

Measured memory_bytes: 256
# coding: utf-8
# Your code here!

# 両方とも正しいならば YES、そうでないならば NO を出力してください。

A, B, C = map(int, input().split())

# print(A)
# print(B)
# print(C)

# 条件を満たす場合はYes、そうでない場合はNoを出力せよ。
if C >= A and C <= B:
 print('Yes')
else:
 print('No')

Measured memory_bytes: 2940
X, N = map(int, input().split())
A = []
if N != 0:
  A = list(map(int, input().split()))
dp = [abs(X-i) for i in range(102)]
for i in range(N):
  dp[A[i]] = int(1e18)
m = int(1e18)
M = 102
for i in range(102, 0, -1):
  if m >= dp[i-1]:
    m = dp[i-1]
    M = i - 1
print(M)

Measured memory_bytes: 9156
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)(x.size())
#define fi first
#define se second
#define pii pair<int, int>

const int N = 1e5 + 10;
int a[N][3], dp[N][3] = {0};
signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i][0] >> a[i][1] >> a[i][2];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                if(j == k) {
                    continue;
                }
                dp[i][j] = max(dp[i][j], dp[i - 1][k] + a[i][j]);
            }
        }
    }
    cout << max(dp[n][0], max(dp[n][1], dp[n][2])) << "\n";
}

Measured memory_bytes: 4992
// https://atcoder.jp/contests/abc146/tasks/abc146_f

#include "algorithm"
#include "cmath"
#include "functional"
#include "iostream"
#include "numeric"
#include "queue"
#include "set"
#include "vector"
#define rep(i, to) for (ll i = 0; i < (to); ++i)
#define repf(i, from, to) for (ll i = from; i < (to); ++i)
#define repr(i, from) for (ll i = from - 1; i >= 0; --i)
#define all(vec) vec.begin(), vec.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
template <typename T>
using V = vector<T>;
using VL = V<ll>;
using VVL = V<VL>;
template <typename T, typename U>
using P = pair<T, U>;
using PL = P<ll, ll>;
using VPL = V<PL>;
template <typename T>
inline bool chmax(T& a, T b);
template <typename T>
inline bool chmin(T& a, T b);
void print_ints(vector<ll> v);
template <typename T>
void drop(T a);

const ll INF = 1e18;

void solve() {
  ll N, M;
  cin >> N >> M;
  string S;
  cin >> S;

  VL rev_steps(0);
  ll cur = N;

  while (cur > 0) {
    ll next_step = M;

    while (cur - next_step < 0 || S[cur - next_step] == '1') {
      next_step--;
      if (next_step == 0) drop(-1);
    }

    rev_steps.push_back(next_step);
    cur -= next_step;
  }

  VL res(rev_steps.size());
  rep(i, rev_steps.size()) { res[rev_steps.size() - 1 - i] = rev_steps[i]; }

  print_ints(res);
}

struct exit_exception : public std::exception {
  const char* what() const throw() { return "Exited"; }
};

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

  try {
    solve();
  } catch (exit_exception& e) {
  }

  return 0;
}
#endif

template <typename T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}

template <typename T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}

void print_ints(vector<ll> v) {
  rep(i, v.size()) {
    if (i > 0) {
      cout << " ";
    }

    cout << v[i];
  }

  cout << endl;
}

template <typename T>
void drop(T res) {
  cout << res << endl;
  throw exit_exception();
}


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

vector<int64_t> memo(87, -1);

int64_t lucas(int n) {
    if (n == 0) {
        memo[0] = 2;
        return memo[0];
    }
    if (n == 1) {
        memo[1] = 1;
        return memo[1];
    }
    if (memo[n] != -1) {
        return memo[n];
    }
    memo[n] = lucas(n - 2) + lucas(n - 1);
    return memo[n];
}

int main() {
  int n;
  cin >> n;
  cout << lucas(n) << endl;
}


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

using namespace std;
using ii = pair<int,int>;
using ll = long long;

ll gauss(ll k) {
  return (k*(1+k)) >> 1;
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  int n; cin >> n;
  long long ans = 0;
  for (int i = 1; i <= n; ++i) {
    ans += gauss(1+n-i);
  }
  for (int i = 1; i < n; ++i) {
    int l, r; cin >> l >> r;
    if (l>r) swap(l,r);
    ans -= (1LL*l*(1+n-r));
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 3588
num, weight = gets.chomp.split(" ").map(&:to_i)
things = Array.new
num.times do
  things << gets.chomp.split(" ").map(&:to_i)
end

# 許容重量ごとの価値の最大値を格納するdp（順次更新）
dp = Array.new(weight + 1, 0)

# 1個目からnum個目までの品物を、ナップサックに入れるべきか順番に確認する
1.upto(num) do |n|
  # n個目の重量をtmp_weight、価値をtmp_valueとする
  tmp_weight = things[n - 1][0]
  tmp_value = things[n - 1][1]
  # 許容重量がweightからtmp_weightまでの場合を、順番に確認する
  # （許容重量がtmp_weight未満の場合、ナップサックに入れることはできないため確認の必要なし）
  # なお、uptoを用いて逆向きに確認すると、ループ中に既に更新した数値を参照してしまうため、正常に動作しない
  weight.downto(tmp_weight) do |w_accepted|
    # 「許容重量がtmp_weight分少ない時の価値 + tmp_value」が「現在格納されている値」よりも大きければ格納する
    if dp[w_accepted] < dp[w_accepted - tmp_weight] + tmp_value
      dp[w_accepted] = dp[w_accepted - tmp_weight] + tmp_value
    end
  end
end

# 最後の品物、最後の許容重量における価値を出力する
puts dp[weight]

Measured memory_bytes: 4604
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"sort"
	"strconv"
)

func main() {
	x := readi()
	n := readi()
	p := make([]int, n)
	for i := 0; i < n; i++ {
		p[i] = readi()
	}

	tmp := INF
	ans := INF
	for i := 101; i >= 0; i-- {
		if !include(p, i) {
			if tmp >= abs(x-i) {
				tmp = abs(x - i)
				ans = min(ans, i)
			}
		}
	}

	fmt.Println(ans)
}

func include(list []int, n int) bool {
	for _, v := range list {
		if v == n {
			return true
		}
	}
	return false
}

/*-------------------utilities-------------------*/

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func chmin(x *int, y int) bool {
	if *x > y {
		*x = y
		return true
	}
	return false
}

func chmax(x *int, y int) bool {
	if *x < y {
		*x = y
		return true
	}
	return false
}

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

func lcm(a, b int) int {
	return (a * b) / gcd(a, b)
}

func permutations(arr []int) [][]int {
	var helper func([]int, int)
	res := [][]int{}

	helper = func(arr []int, n int) {
		if n == 1 {
			tmp := make([]int, len(arr))
			copy(tmp, arr)
			res = append(res, tmp)
		} else {
			for i := 0; i < n; i++ {
				helper(arr, n-1)
				if n%2 == 1 {
					tmp := arr[i]
					arr[i] = arr[n-1]
					arr[n-1] = tmp
				} else {
					tmp := arr[0]
					arr[0] = arr[n-1]
					arr[n-1] = tmp
				}
			}
		}
	}
	helper(arr, len(arr))
	return res
}

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

func divisor(n int) (res []int) {
	for i := 1; i*i <= n; i++ {
		if n%i == 0 {
			res = append(res, i)
			if i*i != n {
				res = append(res, n/i)
			}
		}
	}
	sort.Ints(res)
	return
}

// func searchInts(a []int, k int) int {
// 	return binarySearch(len(a), func(i int) bool {
// 		return a[i] >= k
// 	})
// }

func binarySearch(n int, f func(int) bool) int {
	i, j := 0, n
	for i < j {
		h := int(uint(i+j) >> 1)
		if !f(h) {
			i = h + 1
		} else {
			j = h
		}
	}
	return i
}

/*-------------------init-------------------*/

const (
	INF = 1000000000000000000
	MOD = 1e9 + 7
)

var (
	readString func() string
)

func init() {
	readString = newReadString(os.Stdin)
}

/*-------------------inputs-------------------*/

func readi() int {
	return int(readi64())
}

func readi64() int64 {
	i, err := strconv.ParseInt(readString(), 0, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func readf() float64 {
	f, err := strconv.ParseFloat(readString(), 64)
	if err != nil {
		panic(err.Error())
	}
	return f
}

func newReadString(ior io.Reader) func() string {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	return func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
}


Measured memory_bytes: 1760
#include <iostream>
#include <string>
#include <algorithm>
#include <cassert>
#include <limits>
#include <numeric>
#include <type_traits>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <functional>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <complex>
#include <climits>

using namespace std;

typedef long long ll;
typedef vector<ll> vl;
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define REP(i,n)  FOR(i,0,n)

ll gcd(ll a, ll b) { //gcdを返す
	if(a == 0){
		return b;
	} else if (b == 0){
		return a;
	} else {
	  if(a < b) return gcd(b, a);
	  ll r;
	  while ((r=a%b)) {
	    a = b;
	    b = r;
	  }
	  return b;
	}
}
ll ketasum(ll n) { //桁の数字全ての和を返す 例: 112 -> 4
	ll sum=0;
	if (n<0) return 0;
	while (n>0) {
		sum += n%10;
		n /= 10;
	}
	return sum;
}

typedef pair<ll, ll> pair_t;

bool comp(const pair_t &a, const pair_t &b) {
        return a.first < b.first;
}

void sort2vectors(vector<ll> &av, vector<ll> &bv)
{ // ふたつの配列をまとめてそーと A[2,1] B[3,4] -> 1,4 2,3
        ll n = av.size();
        vector<pair_t> p(n);
        vector<ll> av2(n), bv2(n);
        for (ll i = 0; i < n; i++)
                p[i] = make_pair(av[i], bv[i]);
        sort(p.begin(), p.end(), comp);
        for (ll i = 0; i < n; i++) {
                av2[i] = p[i].first;
                bv2[i] = p[i].second;
        }
        av = av2;
        bv = bv2;
}
ll facctorialMethod(ll k){ //階乗
    ll sum = 1;
    for (ll i = 1; i <= k; ++i)
    {
        sum *= i;
    }
    return sum;
}

int main(){
	ll N, T;
	cin >> N >> T;
	vl c(N);
	vl t(N);
	ll ans = 1001;
	REP(i, N){
		cin >> c[i] >> t[i];
		if(t[i] <= T && c[i] < ans){
			ans = c[i];
		}
	}
	if(ans == 1001){
		cout << "TLE" << endl;
	} else {
		cout <<ans << endl;
	}
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();
// freopen("input.txt", "r", stdin);

int main() {
	int n;
 	char c;
 	cin >> n;
  	while(n--) {
    	cin >> c;
      	if (c == 'Y') {
        	cout << "Four" << endl;
         	return 0;
        }
    }
  	cout << "Three" << endl;
    return 0;
}




Measured memory_bytes: 256
#include<stdio.h>

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


Measured memory_bytes: 2032
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>

using namespace std;
#define int long long int
const int INF = 1001001001001001LL;

int di[] = {-1, 0, 1, 0, -1, 1, 1, -1};
int dj[] = {0, 1, 0, -1, 1, 1, -1, -1};

struct info{
    info(){};
    int l, u, d, r;
};

signed main(){
    
    int h, w; cin >> h >> w;
    vector<vector<int> > g(h + 2, vector<int> (w + 2, 0));
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            char c; cin >> c;
            if(c == '.') g[i][j] = 1;
        }
    }

    vector<vector<info> > ans(h + 2, vector<info> (w + 2));

    for(int i = 1; i <= h; i++){
        int L;
        for(int j = 0; j <= w + 1; j++){
            if(g[i][j] == 0) L = j;
            else ans[i][j].l = L;
        }
        
        int R;
        for(int j = w + 1; j >= 0; j--){
            if(g[i][j] == 0) R = j;
            else ans[i][j].r = R;
        }
    }

    for(int j = 1; j <= w; j++){
        int U;
        for(int i = 0; i <= h + 1; i++){
            if(g[i][j] == 0) U = i;
            else ans[i][j].u = U;
        }

        int D;
        for(int i = h + 1; i >= 0; i--){
            if(g[i][j] == 0) D = i;
            else ans[i][j].d = D;
        }
    }   
    
    int anss = 0;
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            if(g[i][j] == 0) continue;
            info I = ans[i][j];
            int tmp = I.r - I.l - 1 + I.d - I.u - 1 - 1;
            anss = max(anss, tmp);
            
            //cerr << i << " " << j << " " << I.r << " " << I.l << " " << I.u << " " << I.d << endl;
        }
    }

    cout << anss << endl;
    
    return 0;
}


Measured memory_bytes: 156928
/*Alohomora*/
#include<bits/stdc++.h>
#define ll         long long
#define fl(i,n)    for(i=0;i<n;i++)
#define fld(i,a,b) for(i=a;i>b;i--)
#define fli(i,a,n) for(i=a;i<n;i++)
#define inp(i,a,n) for(i=0;i<n;i++) {cin>>a[i];}
#define op(i,a,n)  for(i=0;i<n;i++) {cout<<a[i]<<" ";}
#define pb         push_back
#define mp         make_pair
#define mod1       1000000007
#define speedup    ios_base::sync_with_stdio(false),cin.tie(0)
using namespace std;
ll fact(ll n){ if(n==0){return 1;}return (n*fact(n-1))%mod1;}
ll power(ll x, ll y,ll mod){ll out = 1;while (y > 0){if (y & 1) out=(out*x)%mod;y = y>>1;x = (x*x)%mod;}return out%mod;}
ll inverse(ll a){return power(a,mod1-2,mod1);}
ll gcd(ll a,ll b){if(b==0){return a;}gcd(b,a%b);}
ll a[2000000];
void sieve(){ll i,j;fli(i,2,1000001){if(a[i]==0){for(j=i*i;j<1000001;j+=i){a[j]=1;}}}}
map<ll,vector<ll> >m1;
vector<ll>v1;
bool compar(const pair<ll,ll> &a, const pair<ll,ll> &b) 
{ 
    return (a.second < b.second);
} 
ll level[1000000];
vector<ll>root;
set<ll>s1;
void factorise(long long n) 
{ 
    while (!(n%2)) 
    { 
        n >>= 1; 
        s1.insert(2);
    } 
    for (long long i=3; i<=sqrt(n); i+=2) 
    { 
        while (n%i==0) 
        { 
        	s1.insert(i);
            n=n/i; 
        } 
    } 
  	if (n>2) 
  	{
       s1.insert(n);
	}
} 
void comp()
{
	ll i,j,k,m,n,temp,t1,t2,t3;
	cin>>n;
	ll count=0;
	fl(i,n)
	{
		cin>>j;
		if(i+1!=j)
		{
			count++;
		}
	}
	if(count>2)
	{
		cout<<"NO\n";
	}
	else
	{
		cout<<"YES\n";
	}
}	 
int main()
{
	speedup;
	ll i=0,t;
	ll n;
	//cin>>t;
	t=1;
	while(t--)
	{
	 comp();
	}
}

Measured memory_bytes: 2304
#include <bits/stdc++.h>
using namespace std;
         
    int main() {
        long long N, A, B;
        cin >> N >> A >> B;
        
        long long set;
        set = N / (A+B);

        long long surplus;
        surplus = N % (A+B);

        if(surplus >= A)
            cout << (set + 1) * A << endl;
        else
            cout << set * A + surplus << endl;
    }

Measured memory_bytes: 256
/**
*    author:  yuya1234
*    created: 15.07.2020 11:57:59
**/

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
long double eps = 1.0E-14;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define FORV(i,v) for(auto i=v.begin(); i!=v.end();i++)

#define SORT(s) sort((s).begin(),(s).end())
#define SORTD(s) sort((s).rbegin(),(s).rend())
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define SZ(x) ((int)(x).size())
#define MEMSET(v, h) memset((v), h, sizeof(v))

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 T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<class T>T lcm(T a,T b){return gcd(a,b)*(a/gcd(a,b))*(b/gcd(a,b));}

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  //std::cout << std::fixed << std::setprecision(15);

  string s;
  ll k;
  cin>>s>>k;

  ll cnt=1,sum=0;
  REP(i,SZ(s)-1)
  {
    if(s[i]==s[i+1])cnt++;
    else 
    {
      sum+=cnt/2;
      cnt=1;
    }
  }
  sum+=cnt/2;

  ll cnt1=1;
  REP(i,SZ(s)-1)
  {
    if(s[i]==s[i+1])cnt1++;
    else break;
  }

  if(SZ(s)==cnt) cout<<k*(ll)s.size()/2<<endl;
  else if(s[SZ(s)-1]!=s[0]) cout<<k*sum<<endl;
  else cout<<sum*k-(cnt/2+cnt1/2-(cnt+cnt1)/2)*(k-1)<<endl;

  return 0;
}

Measured memory_bytes: 3652
from collections import deque

n, k = map(int, input().split())
graph = [[] for _ in range(n+1)]
ab_list = []
for i in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    ab_list.append((a, b))

ans = 2000
max_distance = k // 2

if k % 2 == 0:
    for i in range(1, n+1):
        extra_node_cnt = 0
        q = deque()
        q.append((i, 0))
        seen = [0]*(n+1)
        seen[i] = 1
        while q:
            node, distance = q.popleft()
            if distance > max_distance:
                extra_node_cnt += 1
            for neighor_node in graph[node]:
                if seen[neighor_node] == 0:
                    seen[neighor_node] = 1
                    q.append((neighor_node, distance + 1))
        ans = min(ans, extra_node_cnt)
else:
    for now_node, now_neighbor in ab_list:
        extra_node_cnt = 0
        q = deque()
        q.append((now_node, 0))
        seen = [0]*(n+1)
        seen[now_node] = 1
        seen[now_neighbor] = 1
        while q:
            node, distance = q.popleft()
            if distance > max_distance:
                extra_node_cnt += 1
            for neighor_node in graph[node]:
                if seen[neighor_node] == 0:
                    seen[neighor_node] = 1
                    q.append((neighor_node, distance + 1))
        q = deque()
        q.append((now_neighbor, 0))
        seen = [0]*(n+1)
        seen[now_node] = 1
        seen[now_neighbor] = 1
        while q:
            node, distance = q.popleft()
            if distance > max_distance:
                extra_node_cnt += 1
            for neighor_node in graph[node]:
                if seen[neighor_node] == 0:
                    seen[neighor_node] = 1
                    q.append((neighor_node, distance + 1))
        ans = min(ans, extra_node_cnt)

print(ans)

Measured memory_bytes: 57304
#define HAVE_STRUCT_TIMESPEC
#include<bits/stdc++.h>
using namespace std;
long long a[100007];
long long sum[100007];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long n,m,v,p;
    cin>>n>>m>>v>>p;
    for(long long i=1;i<=n;++i)
        cin>>a[i];
    sort(a+1,a+1+n);
    for(long long i=1;i<=n;++i)
        sum[i]=sum[i-1]+a[i];
    long long ans=p;
    if(v<=p){
        long long flag=0;
        for(long long i=1;i<=n-p;++i){
            if(a[i]+m>=a[n-p+1]){
                flag=i;
                break;
            }
        }
        if(flag)
            ans=n-flag+1;
    }
    else{
        long long temp=v-p+1;
        long long flag=0;
        for(long long i=1;i<=n-p;++i){
            long long y=a[i]+m;
            long long z=temp-i;
            if(z>0){
                long long xx=sum[n-p+1]-sum[i];
                xx+=m*z;
                long long now=y*(n-p+1-i);
                if(xx<=now&&y>=a[n-p+1]){
                    flag=i;
                    break;
                }
            }
            else{
                if(y>=a[n-p+1]){
                    flag=i;
                    break;
                }
            }
        }
        if(flag)
            ans=n-flag+1;
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 1792
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
signed main() {
	ios::sync_with_stdio(false); cin.tie(0);
	long long a, b, c;
	cin >> a >> b >> c;
	cout << min({c % 2 * a * b, a % 2 * c * b, b % 2 * a * c}) << endl; 
	return 0;	
}


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

int main(){
  int n, a, ans = 0;
  cin >> n;
  for(int i = 0; i < n; i++) {
    cin >> a;
    if(!(i % 2) && a % 2) ans++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3640
solver :: Int -> Int -> Int -> Int -> Int
solver a b c d =
  let d_ab x = (div b x) - (div (a - 1) x)
   in (b - a + 1) - ((d_ab c) + (d_ab d) - (d_ab (lcm c d)))

main :: IO ()
main = do
  a:b:c:d:_ <- map read . words <$> getLine
  print $ solver a b c d


Measured memory_bytes: 508
N, K = map(int, input().split())

x, y = 0, 0

for i in range(1, N + 1):
    if i % K == 0:
        x += 1
    if K % 2 == 0 and i % K == K // 2:
        y += 1

print(x ** 3 + y ** 3)


Measured memory_bytes: 2940
#include <cstdlib>
#include <iostream>
#include <string>
#include <time.h>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <iomanip>
#include <vector>
#include <functional>
//#include "bits/stdc++.h"
using namespace std;
//using namespace std::vector;
#define rep(i,a,b) for(int i=(a);i<(b);++i)


#define huge 1000000007
typedef long long ll;

int main(void) {

	ll N = 0;
	ll A = 0;
	ll B = 0;
	ll C = 0;
	ll X = 0;
	ll M = 0;
	ll Q = 0;
	//double a[100000] = {};
	//double b[100000] = {};
	//ll v[100] = {};
	ll *p, *c, *d;
	string S,T,U;
	ll count = 0;
	ll sum = 0;
	ll min = 100000;
	ll max = 0;
	int flag = 0;
	char temp,head;
	//int is = 0;


	//char p;
	cin >>A >> B;
	//cin >> D >> G;
	vector<pair<int,int>> tr(M);
	vector<pair<int,int>> qes(Q);

	

	//sort(is.begin(), is.end());
	//p = (ll *)malloc(D * sizeof(ll));
	//c = (ll *)malloc(D * sizeof(ll));
	//d = (ll *)malloc(D * sizeof(ll));

	if (A % 2 == 0 || B % 2 == 0) {
		cout << "No" << endl;
	}
	else {
		cout << "Yes" << endl;
	}


	
	//sort(l,l+N);


	return 0;

}



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

int main()
{
   int a,b,x;
   cin>>a>>b>>x;
   if(a<=x){
       if(a+b>=x){
           std::cout << "YES" << std::endl;
       }
       else{
           std::cout << "NO" << std::endl;
       }
   }
   else{
       std::cout << "NO" << std::endl;
   }
   return 0;
}


Measured memory_bytes: 3572
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M = 2e5 + 100;
const ll mod = 998244353;
ll fac[M];
int n, m, k;
ll add(ll a, ll b) {
    return (a+b) % mod;
}
ll mul(ll a, ll b) {
    return (a*b) % mod;
}
ll fpow(ll a, ll b) {
    ll ans = 1;
    while(b) {
       if(b&1) {
           ans = mul(ans, a);
       }
       b >>= 1;
       a = mul(a, a);
    }
    return ans;
}
ll inv(ll a) {
    return fpow(a, mod-2);
}
ll c(ll n, ll m) {
    return mul(fac[n], mul( inv(fac[m]), inv(fac[n-m]) )  );
}
void init() {
    fac[0] = 1;
    for(int i=1;i<M;i++) fac[i] = mul(fac[i-1], i);
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    init();
    //cout<<c(10,3)<<endl;
    cin>>n>>m>>k;
    ll ans = 0;
    for(int i=0;i<=k;i++) {
        ans = add(ans, mul(m, mul(c(n-1, i), fpow(m-1, n-1-i))));
    }
    cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 5212
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <bitset>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring> 
#include <iostream>
#include <algorithm>
using namespace std;

long long N, K, ans = 0;
long long A[200005];
long long lim = 0;

inline bool check(long long x)
{
	long long ret = 0;
	for(int i = 1;i <= N;++i)
	{
		int t = A[i] / x + (A[i] % x != 0);
		ret += t - 1;
	}
	if(ret > K)
		return false;
	return true;
}

int main()
{
	cin >> N >> K;
	for(int i = 1;i <= N;++i)
	{
		cin >> A[i];
		lim = max(lim, A[i]);
	}
	long long l = 1, r = 1000000000;
	while(r - l > 1)
	{
		long long mid = (l + r) >> 1;
		if(check(mid))
			ans = mid, r = mid;
		else
			l = mid + 1;
	}
	if(check(l))
		ans = l;
	else
		ans = r;
	cout << ans << endl;
}


Measured memory_bytes: 5124
/*
 * @Author: AsilenceBTF
 * @Buff: ︿(￣︶￣)︿  芜湖塔台 起飞
 * @Date: 2019-06-20 09:22:24
 * @LastEditTime: 2020-09-21 15:04:55
 */
#include <bits/stdc++.h>
using namespace std;
#define sz(x) int(x.size())
#define ALL(x) x.begin(), x.end()
#define INF 0x3f3f3f3f
#define debug(x) cout << "##### " << x << endl; 
typedef long long ll;

const int N = 1e7 + 105;

int main(){
    string s;
    cin >> s;
    if(s.back() == 's') s += "es";
    else s += "s";
    cout << s << endl;
    // system("pause");
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define int long long
#define MAXN 200005
#define mod 1000000007
using std::vector;
int n,i,x,f[MAXN],size[MAXN];
vector<int> G[MAXN];
bool vis[MAXN];
inline void read(int &x)
{
	short negative=1;
    x=0;
    char c=getchar();
    while(c<'0' || c>'9')
    {
    	if(c=='-')
			negative=-1;
		c=getchar();
	}
    while(c>='0' && c<='9')
        x=(x<<3)+(x<<1)+(c^48),c=getchar();
    x*=negative;
}
inline void print(int x)
{
    if (x<0)
        putchar('-'),x=-x;
    if (x>9)
        print(x/10);
    putchar(x%10+'0');
}
inline int ksm(int a,int n,int p)
{
	int Ret(1);
	while (n)
	{
		if (n&1)
			(Ret*=a)%=p;
		(a*=a)%=p,n>>=1;
	}
	return Ret;
}
inline void dfs(int u)
{
	vis[u]=true,size[u]=1;
	for (int i=0;i<G[u].size();i++)
	{
		int v=G[u][i];
		if (vis[v])
			continue;
		dfs(v);
		size[u]+=size[v];
	} 
	(f[1]*=size[u])%=mod;
}
inline void dfs2(int u)
{
	vis[u]=true;
	for (int i=0;i<G[u].size();i++)
	{
		int v=G[u][i];
		if (vis[v])
			continue;
		f[v]=f[u]*((n-size[v])*ksm(size[v],mod-2,mod)%mod)%mod;
		dfs2(v);
	}
}
signed main(void)
{
	read(n);
	for (i=1;i<n;i++)
	{
		int u,v;
		read(u),read(v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	f[1]=1;
	dfs(1);
	memset(vis,false,sizeof(vis));
	dfs2(1);
	for (i=x=1;i<=n;i++)
		(x*=i)%=mod;
	for (i=1;i<=n;i++)
		print((x*ksm(f[i],mod-2,mod))%mod),putchar('\n');
	return 0;
}

Measured memory_bytes: 18032
/*
    to amy
*/

#include <bits/stdc++.h>
#define MAX 100010
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n,x,sum,min_,k,t;
    while(cin>>n){
        vi v;
        sum = 0;
        for(int i=0;i<n;i++){
            cin>>x;
            v.pb(x);
            sum+=x;
        }
        min_ = 100000;
        t = 0;
        for(int i=v.size()-1;i>0;i--){
            t += v[i];
            k = abs((sum - t)-t);
            if(k<min_) min_ = k;
        }
        cout<<min_<<endl;
    }

    return 0;
 
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int k,l,cnt;
char s[5005];
string ch[5005*6];
int main(){
	scanf("%s%d",s,&k);
	l=strlen(s);
	for(int i=0,T;i<l;++i){
		ch[++cnt]=s[i];
		T=min(k,l-i);
		for(int j=1;j<T;++j,++cnt)ch[cnt+1]=ch[cnt]+s[i+j];
	}
	sort(ch+1,ch+cnt+1);
	unique(ch+1,ch+cnt+1);
	cout<<ch[k];
}

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

using namespace std;

typedef long long ll;
const ll INF=1e18+10;
const ll N=1e2+10;

ll d[N][N];
ll V,E;

void init()
{
    for(ll i=0;i<V;i++)
    {
        for(ll j=0;j<V;j++)
        {
            d[i][j]=INF;
            if(i==j) d[i][j]=0;
        }
    }
}

bool Floyd()
{
    for(ll k=0;k<V;k++)
    {
        for(ll i=0;i<V;i++)
        {
            for(ll j=0;j<V;j++)
            {
                if(d[i][j]>d[i][k]+d[k][j]&&d[i][k]!=INF&&d[k][j]!=INF)
                {
                    d[i][j]=d[i][k]+d[k][j];
                }
                if(i==j&&d[i][j]<0) return true;
            }
        }
    }
    return false;
}

int main()
{
    while(scanf("%lld %lld",&V,&E)!=EOF)
    {
        ll s,t,c;
        init();
        for(ll i=0;i<E;i++)
        {
            scanf("%lld %lld %lld",&s,&t,&c);
            d[s][t]=c;
        }
        if(Floyd())
        {
            puts("NEGATIVE CYCLE");
            continue;
        }
        for(ll i=0;i<V;i++)
        {
            for(ll j=0;j<V;j++)
            {
                if(j)
                {
                    printf(" ");
                }
                if(d[i][j]==INF)
                {
                    printf("INF");
                }else
                {
                    printf("%lld",d[i][j]);
                }
            }
            printf("\n");
        }
    }
}



Measured memory_bytes: 3320
//-----by LY02------------------------------------
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
//------------------------------------------------

int w[110],v[110];
long long dp[110][100010];

//------------------------------------------------
int main() {
//------------------------------------------------
//	freopen("In.txt","r",stdin);
//	freopen("Out.txt","w",stdout);
//------------------------------------------------
	ios::sync_with_stdio(0);
	cin.tie(0);
//------------------------------------------------

int n,k;
cin>>n>>k;

for(int i=0;i<n;i++)
	cin>>w[i]>>v[i];
memset(dp,-1,sizeof(dp));
dp[0][0]=0;
dp[0][v[0]]=w[0];
for(int i=1;i<n;i++)
{
	for(int j=0;j<=100000;j++)
	{
		if(dp[i-1][j]==-1) continue;
		dp[i][j]=min(dp[i-1][j] , dp[i][j]==-1?dp[i-1][j]:dp[i][j]);
		if(dp[i-1][j]+w[i]>k) continue;
		dp[i][j+v[i]]=max(dp[i-1][j]+w[i] , dp[i][j+v[i]]==-1?dp[i-1][j]+w[i]:dp[i][j+v[i]]);
	}
//	cout<<i<<" : \n";
//	for(int j=0;j<=100000;j++)
//	{
//		if(dp[i][j]==-1) continue;
//		cout<<j<<" "<<dp[i][j]<<endl;
//	}
}
long long ans=0;
int nw=INT_MAX;
for(int i=0;i<=100000;i++)
{
	if(dp[n-1][i]==-1) continue;
	ans=i;
}
cout<<ans<<endl;

//------------------------------------------------
	return 0;
}





//-----by LY02------------------------------------


Measured memory_bytes: 86272
#include <iostream>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <algorithm>
#include <bitset>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#define INF 100000000000
#define MOD 1000000007
#define ll long long int
//#define int long long int
using namespace std;
int N;

void dfs(string s,char mx){
  if(s.length() == N) printf("%s\n",s.c_str());
  else {
    for(char c = 'a' ; c<= mx ; c++){
      dfs(s + c,((c==mx) ? (char)(mx + 1) : mx));
    }
  }

}

int main(){
  cin>>N; 
  dfs("",'a');
  return 0;

}



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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    vector<int> h(n);
    for(int i = 0; i < n; ++i) cin >> h[i];
    int sum;
    int ans = 0;
    do {
        sum = 0;
        int noc = 0;
        bool seen = false;
        for(int i = 0; i < n; ++i) {
            if(seen == false && h[i] > 0) noc += 1, seen = true;
            if(h[i] == 0) seen = false;
            sum += h[i];
            h[i] = max(h[i] - 1, 0);
        }
        ans += noc;
    } while(sum > 0);
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>
using namespace std;
typedef pair<int, int> pii;
const int inf = 1e9;

struct state{
    int p;
    int c;
    int get;
    int cpl;
    state(int p, int c, int g, int cp):
        p(p),c(c),get(g),cpl(cp){}
    state();
    bool operator <(const state &a) const{
        return c > a.c;
    }
};

int main(){
    int n,m,k,p;
    cin >> n >> m >> k >> p;
    p--;
    vector<vector<pii>> adj(n);
    for(int i=0; i<m; i++){
        int x,y,c;
        cin >> x >> y >> c;
        x--; y--;
        adj[x].emplace_back(y, c);
        adj[y].emplace_back(x, c);
    }
    vector<int> s(k), t(k);
    for(int i=0; i<k; i++){
        cin >> s[i] >> t[i];
        s[i]--; t[i]--;
    }

    priority_queue<state> wait;
    wait.push(state(p, 0, 0, 0));
    vector<vector<vector<int>>> dp(n, vector<vector<int>>(1<<k, vector<int>(1<<k, inf)));
    dp[p][0][0] = 0;
    while(!wait.empty()){
        int p = wait.top().p;
        int c = wait.top().c;
        int get = wait.top().get;
        int cpl = wait.top().cpl;
        wait.pop();
        if(c > dp[p][get][cpl]) continue;
        for(pii next: adj[p]){
            int np = next.first;
            int nc = c + next.second;
            int nget = get;
            int ncpl = cpl;
            for(int i=0; i<k; i++){
                if(np == s[i]){
                    nget |= 1<<i;
                }
                if(np == t[i] and (nget>>i&1)){
                    ncpl |= 1<<i;
                }
            }
            if(nc < dp[np][nget][ncpl]){
                dp[np][nget][ncpl] = nc;
                wait.push(state(np, nc, nget, ncpl));
            }
        }
    }
    int ans = inf;
    for(auto vv: dp){
        for(auto v: vv){
            ans = min(ans, v[(1<<k)-1]);
        }
    }
    if(ans == inf){
        cout << "Cannot deliver" << endl;
    }else{
        cout << ans << endl;
    }
    return 0;
}



Measured memory_bytes: 22572
a=list(map(int, input().split()))
s=[[1,3,5,7,8,10,12],[4,6,9,11],[2]]
ans=[]
for i in a:
  for j in range(len(s)):
    if i in s[j]:
      ans.append(j)
      break
if len(set(ans))==1:
  print('Yes')
else:
  print('No')

Measured memory_bytes: 3064