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

#define _p(...) (void)printf(__VA_ARGS__)
#define forr(x,arr) for(auto&& x:arr)
#define _overload3(_1,_2,_3,name,...) name
#define _rep2(i,n) _rep3(i,0,n)
#define _rep3(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,_rep3,_rep2,)(__VA_ARGS__)
#define _rrep2(i,n) _rrep3(i,0,n)
#define _rrep3(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define rrep(...) _overload3(__VA_ARGS__,_rrep3,_rrep2,)(__VA_ARGS__)
#define ALL(x) (x).begin(), (x).end()
#define BIT(n) (1LL<<(n))
#define SZ(x) ((int)(x).size())
#define fst first
#define snd second
using ll=long long;using pii=pair<int,int>;using vb=vector<bool>;
using vi=vector<int>;using vvi=vector<vi>;using vvvi=vector<vvi>;
using vl=vector<ll>;using vvl=vector<vl>;using vvvl=vector<vvl>;
using vd=vector<double>;using vvd=vector<vd>;using vvvd=vector<vvd>;
using vpii=vector<pii>;using vvpii=vector<vpii>;using vvvpii=vector<vvpii>;
template <typename T> T read() {T t; cin >> t; return t;}

void Main() {
  string s = read<string>();
  int ans = 0;
  forr(c, s) {
    if (c == 'g') ans++;
    else ans--;
  }
  cout << ans/2 << endl;
}
int main() { cin.tie(nullptr); ios::sync_with_stdio(false); Main(); return 0; }


Measured memory_bytes: 512
#include <iostream>
#include <cstdio>
#define int long long
#define N 100052
using namespace std;
const int mod=1000000007;
int n,m,i,f[N],prime[N],num[N],cnt;
int read()
{
	char c=getchar();
	int w=0;
	while(c<'0'||c>'9') c=getchar();
	while(c<='9'&&c>='0'){
		w=w*10+c-'0';
		c=getchar();
	}
	return w;
}
int poww(int a,int b)
{
	int ans=1,base=a;
	while(b){
		if(b&1) ans=ans*base%mod;
		base=base*base%mod;
		b>>=1;
	}
	return ans%mod;
}
int C(int m,int n)
{
	return f[n]*poww(f[m],mod-2)%mod*poww(f[n-m],mod-2)%mod;
}
signed main()
{
	n=read();m=read();
	f[0]=1;
	for(i=1;i<=n+50;i++) f[i]=f[i-1]*i%mod;
	for(i=2;i*i<=m;i++){
		if(m%i==0) prime[++cnt]=i;
		while(m%i==0) num[cnt]++,m/=i;
	}
	if(m!=1) prime[++cnt]=m,num[cnt]=1;
	long long ans=1;
	for(i=1;i<=cnt;i++) ans=ans*C(n-1,n+num[i]-1)%mod;
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 1024
#include<stdio.h>
main(){
  int n,a=100000,c,i,j,k;
  double b;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    a = a*1.05;
    if(a%1000!=0){
      b = a/1000;
      b = b+1;
      b = ceil(b);
      a = b*1000;
    }      
  }
  printf("%d\n",a);
  return 0;
}

Measured memory_bytes: 596
;; -*- coding: utf-8 -*-
(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0)))
  #+swank (progn (ql:quickload '(:cl-debug-print :fiveam))
                 (shadow :run)
                 (use-package :fiveam)))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)

;; BEGIN_INSERTED_CONTENTS
(defmacro dbg (&rest forms)
  #+swank
  (if (= (length forms) 1)
      `(format *error-output* "~A => ~A~%" ',(car forms) ,(car forms))
      `(format *error-output* "~A => ~A~%" ',forms `(,,@forms)))
  #-swank (declare (ignore forms)))

(defmacro define-int-types (&rest bits)
  `(progn
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits)
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits)))
(define-int-types 2 4 7 8 15 16 31 32 62 63 64)

(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
  (let ((*read-default-float-format* 'double-float))
    (prog1 (princ obj stream) (terpri stream))))

(defconstant +mod+ 1000000007)

;; Body

(defun main ()
  (let* ((n (read)))
    (dotimes (_ n (write-line "second"))
      (when (oddp (read))
        (write-line "first")
        (return-from main)))))

#-swank(main)


Measured memory_bytes: 57828
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
#define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++)
#define per(i,j,k) for(int i = (int)j;i >= (int)k;i --)
#define debug(x) cerr<<#x<<":"<<x<<endl
#define pb push_back
#define FAST_IO ios::sync_with_stdio(0); cin.tie(0)
#define Decimal fixed<<setprecision(20)
#define int long long
//INSERT ABOVE HERE
typedef double db;

signed main(){
    FAST_IO;
    int n;
    cin>>n;
    stack<int>S;
    int ans=0;
    int last=(int)1e9+5;
    int cnt=0;
    rep(i,1,n){
        int x;
        cin>>x;
        if(x<=last)cnt++;else cnt=1;
        last=x;
        chmax(ans,cnt);
    }
    cout<<ans-1<<endl;
}
/*
1
1 1
6
0 0 2
0 1 1
1 0 1
1 1 3
2 0 3
2 1 2


*/


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
 
typedef long long ll;
 
int main() {
    int D, N;
    cin >> D >> N;
    if (N == 100) N = 101;
    cout << N;
    rep(i, D) cout << "00";
    cout << endl;
}

Measured memory_bytes: 256
import string
n = input()
s = input()
list = list(string.ascii_uppercase)
list.extend(list)
newlist = []
for al in s:
  initloc = list.index(al)
  nowloc = int(initloc) + int(n)
  
  newlist.append(list[nowloc])
print("".join(newlist))

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

int main(){
   long long N,K;
   cin >> N >> K;
   if(N > K * 3){
       N = N - ((N / K) - 3) * K;
   }
   while(true){
   if(N > abs(N - K)){
       N = abs(N - K);
   }else{
       break;
   }
   }
   cout << N << endl;
}

Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define sz size()
#define pb push_back
const ll mod = 1e9 + 7;
double n, c[501], s[501], f[501];
double ans;

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin>>n;
    for(int i=1; i<=n-1; i++) cin>>c[i]>>s[i]>>f[i];
    for(int i=1; i<=n-1; i++){
        ans=s[i]+c[i]; for(int j=i+1; j<=n-1; j++){
            if(ans<=s[j]) ans=s[j]+c[j]; else ans=(ceil(ans/f[j])*f[j])+c[j];
        }
        cout<<ans<<endl;
    } cout<<0;
}

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

using namespace std;
long long dp[305][305][305],l,r,x,n,m,mod;
vector<pair<int,int> > a[305];
long long dq(int i,int v1,int v2,int v3)
{
    bool kt=true;
    int l,mau;
    for (int j=0;j<a[i-1].size();++j)
    {
        l=a[i-1][j].first;
        mau=a[i-1][j].second;
        if (v1>=l) mau--;
        if (v2>=l) mau--;
        if (v3>=l) mau--;
        if (mau!=0) {kt=false;break;}
    }
    if (!kt) return 0;
    if (i>n) return 1;
    if (dp[v1][v2][v3]!=-1) return dp[v1][v2][v3];
    long long k=(dq(i+1,i,v2,v3)+dq(i+1,v1,i,v3)+dq(i+1,v1,v2,i))%mod;
    return dp[v1][v2][v3]=k;

}
int main()
{
   

    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;mod=1000000007;
    for (int i=1;i<=m;++i)
    {
        cin>>l>>r>>x;
        a[r].push_back({l,x});
    }
    memset(dp,-1,sizeof(dp));
    cout<<dq(1,0,0,0);

    return 0;
}


Measured memory_bytes: 221952
#include<iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <tuple>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
using namespace std;

#define ll int64_t
const long MOD = 1e9 + 7;


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

    cout << n*(n+1)/2;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <stack>
#include <functional>

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) 42
#endif

#define rep_(i, a_, b_, a, b, ...) for (int i = (a), i##_len = (b); i < i##_len; ++i)
#define rep(i, ...) rep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define reprev_(i, a_, b_, a, b, ...) for (int i = (b-1), i##_min = (a); i >= i##_min; --i)
#define reprev(i, ...) reprev_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define all(x) (x).begin(), (x).end()
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; }
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int,int> P;
typedef long double ld;

int main (void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a, b; cin >> a >> b;
    cout << a * b << "\n";
    return 0;
}

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

#define PI 3.141592

using namespace std;

struct Monster{
    int life,attack;
};

int main (void){
    Monster monster[2];
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    monster[0]={a,b};//takahashi
    monster[1]={c,d};//aoki
    while(monster[0].life>0&&monster[1].life>0){
        monster[1].life-=monster[0].attack;
        if(monster[1].life>0){
            monster[0].life-=monster[1].attack;
        }
    }
    if(monster[0].life>0){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
    return 0;
}

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

using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;

int main() {

    int n; cin >> n;

    vector<int> x(n);
    vector<int> y(n);
    vector<int> h(n);
    for (int i = 0; i < n; ++i) {
        cin >> x[i] >> y[i] >> h[i];
    }

    for (int cx = 0; cx <= 100; ++cx) {
        for (int cy = 0; cy <= 100; ++cy) {
            int H;
            for (int i = 0; i < n; ++i) {
                if (h[i] != 0) {
                    H = h[i] + abs(x[i] - cx) + abs(y[i] - cy);
                }
            }

            bool ok = true;
            for (int i = 0; i < n; ++i) {
                if (h[i] != max(H - abs(x[i] - cx) - abs(y[i] - cy), 0)) {
                    ok = false;
                }
            }

            if (ok) {
                cout << cx << " " << cy << " " << H << endl;
                return 0;
            }
        }
    }
}

Measured memory_bytes: 3584
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long m = sc.nextLong();
        long n = sc.nextLong();
        System.out.println(lcm(m,n));
        sc.close();
    }

    private static long gcd(long m, long n) {
        if(m < n) return gcd(n, m);
        if(n == 0) return m;
        return gcd(n, m % n);
    }

    private static long lcm(long m, long n) {
        return m * n / gcd(m, n);
    }

}


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

#define INF 1001001001
#define LINF 1001001001001001001
#define MOD 1000000007
#define MOD2 998244353

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

#define rep(i,n) for(int i=0,_i=(n);i<_i;++i)
#define rep1(i,a,b) for(int a_=(a),b_=(b),i=a_;i<b_;++i)
#define repr(i,n) for(int _i=(n),i=_i;i>0;--i)

#define db(x) cerr<<#x<<" = "<<x<<" ";
#define db2(x,y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<") ";
#define ln cout<<endl;

#define all(a)  (a).begin(),(a).end()
#define dig(n)  to_string(n).length()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define se second
#define fi first

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

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return (a*b)/gcd(a,b);}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};



int main(){

    bool flag=false;
    ll ans=0,sum=0;

    int k,x;
    cin >>k>>x;
    //cout <<fixed<<setprecision(16)<< << endl;
    //cout<<ans<<endl;
    if(k*500 >= x)cout << "Yes" <<endl;
    else cout << "No" <<endl;
    
    return 0;
}


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

int main(){
    int H = 0,N = 0;
    cin >> H >> N;
    
    vector<int> AT(N,0);
    vector<int> MP(N,0);

    for(int i=0;i<N;i++)cin >> AT[i] >>MP[i];
    int maxat = *max_element(AT.begin(),AT.end());



    vector<int> HE(H+2*maxat,1000000000);
    HE.at(0) = 0;
    for(int i = 0; i <= H+maxat; i++){                      
        for(int j = 0;j<N;j++){
            if(i+AT.at(j) >= H+2*maxat)continue;
                HE.at(i+AT.at(j)) = min(HE.at(i)+MP.at(j),HE.at(i+AT.at(j)));
        }
    }
    int minmp = *min_element(HE.begin() + H, HE.end());
    cout << minmp << endl;  //出力の最後は改行する必要があります


}


Measured memory_bytes: 384
using System.Linq;
using System;

public class hello
{
    public static void Main()
    {
        var n = int.Parse(Console.ReadLine().Trim());
        string[] line = Console.ReadLine().Trim().Split(' ');
        var a = Array.ConvertAll(line, int.Parse);
        Console.WriteLine((a.Max() - a.Min() + 1) / 2);
    }
}



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

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

bool f(const string &s){
  // cout<< s<< endl;
  if(s=="ABC") return true;
  if(s.size()<=3) return false;
  int n=s.size();
  char c;
  if(s.substr(0, 3)=="ABC") c='A';
  else if(s.substr(n-3, 3)=="ABC") c='C';
  else c='B';
  string t="";
  rep(i, n){
    if(s.substr(i, 3)=="ABC"){
      t+=c;
      i+=2;
    }else{
      t+=s[i];
    }
  }
  if(s.size()==t.size()) return false;
  string u="";
  int m=t.size();
  rep(i, m){
    if(t[i]==c){
      u+="ABC";
    }else{
      u+=t[i];
    }
  }
  if(s==u) return f(t);
  else return false;
}

int main(){

  string s; cin>> s;

  bool ok=f(s);
  if(ok) cout<< "Yes"<< endl;
  else cout<< "No"<< endl;

  // cout<< ret<< endl;

  return 0;
}


Measured memory_bytes: 27852
def submit():
    n = int(input())
    a = list(map(int, input().split()))

    # dp[i][j] : i ~ j - 1までの数列におけるX - Yのスコア
    # taroのターンの場合、
    #   max(dp[i + 1][j] + iスコア, dp[i][j - 1] + jスコア)
    # jiroのターンの場合
    #   min(dp[i + 1][j] - iスコア, dp[i][j - 1] - jスコア)

    dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][i] = 0

    # len = 1, 2, 3, ...と求めてゆく
    # len = xのとき、dp[i + 1][j]かdp[i][j - 1]はlen = x - 1のときのスコアなので
    # 計算済み
    for l in range(1, n + 1):
        for i in range(n):
            j = i + l
            if j > n:
                break
            
            # taroのターン, nとlの偶奇が一致する時
            if (n - l) % 2 == 0:
                dp[i][j] = max(dp[i + 1][j] + a[i], dp[i][j - 1] + a[j - 1])
            else:
                dp[i][j] = min(dp[i + 1][j] - a[i], dp[i][j - 1] - a[j - 1])

    print(dp[0][n])
            

submit()

Measured memory_bytes: 120156
const main = (input) => {
  const s = parseInt(input.trim(), 10)
  let m = 0
  while (s > m) {
    m += 1000
  }

  return  console.log(m - s)
}

process.env.MYTEST ? test() : main(require('fs').readFileSync('/dev/stdin', 'utf8'))

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

int main()
{
    long long H, N;
    std::cin >> H >> N;

    std::vector<long long> A(N);
    for (int i = 0; i < N; i++)
        std::cin >> A[i];
    
    long long sum_num = 0;
    for (int i = 0; i < N; i++)
        sum_num += A[i];
    
    if (sum_num >= H)
        std::cout << "Yes" << std::endl;
    else
        std::cout << "No" << std::endl;

    return 0;
}

Measured memory_bytes: 1024
H, W = map(int, input().split())
N = 0
coins = []
ans = []

for i in range(H):
  coin = list(map(int, input().split()))
  coins.append(coin)

for i in range(H):
    for j in range(W-1):
      if coins[i][j] % 2 == 1:
        N += 1
        coins[i][j] -= 1
        coins[i][j+1] += 1
        ans.append([i,j,i,j+1])
        
for i in range(H-1):
  if coins[i][W-1] % 2 == 1:
    N += 1
    coins[i][W-1] -= 1
    coins[i+1][W-1] += 1
    ans.append([i, W-1, i+1, W-1])
    
print(N)
for i in range(N):
    print(ans[i][0]+1,ans[i][1]+1, ans[i][2]+1,ans[i][3]+1)
        
        

Measured memory_bytes: 26408
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author cunbidun
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        BSumo solver = new BSumo();
        solver.solve(1, in, out);
        out.close();
    }

    static class BSumo {
        private InputReader in;
        private PrintWriter out;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            this.in = in;
            this.out = out;
            String S = in.nextString();
            int cnto = StringAlgorithm.count(S, 'o');
            if (cnto + 15 - S.length() >= 8) out.println("YES");
            else out.println("NO");
        }

    }

    static class InputReader extends InputStream {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public String nextString() {
            int c;
            while (isSpaceChar(c = read())) ;
            StringBuilder result = new StringBuilder();
            result.appendCodePoint(c);
            while (!isSpaceChar(c = read()))
                result.appendCodePoint(c);
            return result.toString();
        }

        private static boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

    }

    static class StringAlgorithm {
        public static int count(String S, int stIndex, int enIndex, char c) {
            int cnt = 0;
            for (int i = stIndex; i <= enIndex; i++) {
                if (S.charAt(i) == c) cnt++;
            }
            return cnt;
        }

        public static int count(String S, char c) {
            return count(S, 0, S.length() - 1, c);
        }

    }
}



Measured memory_bytes: 22868
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main() {
    int a1;
    int a2;
    int a3;
    cin  >> a1 >> a2 >> a3;
    vector<int> vec;
    vec.push_back(a1);
    vec.push_back(a2);
    vec.push_back(a3);
    sort(vec.begin(), vec.end(), greater<int>());
    int i;
    int sum = 0;
    for(i = 1;i < vec.size(); i++){
        sum += abs(vec[i] - vec[i - 1]);
    }

    cout << sum << endl;


    return 0;
}

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

using namespace std;

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

    map<char, int> counter;
    for (auto c : str) {
        if (counter.count(c) == 0) {
            counter[c] = 1;
        } else {
            counter[c]++;
        }
    }

    string ans = "Yes";
    for (auto itr : counter) {
        int count = itr.second;

        if (count % 2 == 1) {
            ans = "No";
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<cmath>
#include<ctime>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<set>
#include <cstdio>
#include <string>
#include <unordered_map>
using namespace std;
const int N = 1e5 +1;
int n, m, tot;
int a[N * 2][2], w[N], r[N], d[N], in[N], rr[N];
int ans;
void ins(int x, int y)
{
    a[++tot][0] = y, a[tot][1] = w[x], w[x] = tot;
    a[++tot][0] = x, a[tot][1] = w[y], w[y] = tot;
}
void dfs(int x)
{
    for (int i = w[x]; i ;w[x] = i = a[i][1])
        if (a[i][0])
        {
            int y = a[i][0];
            a[i][0] = a[i ^ 1][0] = 0;
            w[x] = i;
            dfs(y);
            if (i > w[x]) i = w[x];
        }
    d[++ d[0]] = x;
}
int main(){
    scanf("%d %d", &n, &m);
    tot = 1;
    for (int i = 1; i <= m ; i ++){
        int x, y;
        scanf("%d %d", &x, &y);
        in[x] ++;
        in[y] ++;
        ins(x, y);
    }
    for (int i  = 1; i <= n  ; i ++)
        if (in[i]&1)
        {
            printf("No\n");
            return 0;
        }
    dfs(1);
    int r_min = d[0] + 1;
    int r_max = 0;
    for (int i = d[0]; i > 1; i --) {
        if (!rr[d[i]]) rr[d[i]] = i;
        if (r_min <= rr[d[i]])
        {
            printf("Yes");
            return 0;
        }
        if (r[d[i]]) {
            r_min = min(r_min, r[d[i]]);
            if (!r_max) r_max = i;
        }
        if (r[d[i]]&& r[d[i]] <= r_max)
        {
            printf("Yes");
            return 0;
        }
        r[d[i]] = i;
    }
    printf("No");
    return 0;
}

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

vector<int> sieve(int n) {
  vector<int> prime(n);
  for(int i=2; i<n; i++) prime[i]=i;
  for(int i=2; i*i<n; i++) {
    if(prime[i]) {
      for(int j=i*i; j<n; j+=i) prime[j]=0;
    }
  }
  prime.erase(remove(prime.begin(), prime.end(), 0), prime.end());
  return prime;
}

int main() {
  vector<int> prime=sieve(1000000);
  while(1) {
    int n, cnt=0;
    cin >> n;
    if(n==0) break;
    int check=0;
    for(vector<int>::iterator it=prime.begin(); *it<=n/2; it++) {
      int x=*it, t;
      t=distance(prime.begin(), lower_bound(prime.begin(),prime.end(), n-x));
      if(x+prime[t]==n) cnt++;
    }
    cout << cnt << endl;
  }
  return 0;
}


Measured memory_bytes: 4900
import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
      	int b = sc.nextInt();
      	int c = sc.nextInt();
      	int d = sc.nextInt();
      int x = Math.abs(b-a);
      int y = Math.abs(c-b);
      int z = Math.abs(c-a);
      
      if(x<=d&&y<=d){System.out.println("Yes");}
      else if(z<=d){System.out.println("Yes");}
      else{System.out.println("No");}
      
    }
}

Measured memory_bytes: 22996
dp_n = 410
n, ma, mb = map(int, input().split())
dp = [[float('inf')]*dp_n for _ in range(dp_n)]
dp[0][0] = 0
for i in range(n):
    a, b, c = map(int, input().split())
    for j in reversed(range(dp_n)):
        for i in reversed(range(dp_n)):
            if dp[i][j] != float('inf'):
                try:
                    dp[i+a][j+b] = min(dp[i+a][j+b],dp[i][j]+c)
                except:
                    pass
res = float('inf')
for j in range(1,dp_n):
    for i in range(1,dp_n):
        if i*mb == j*ma:
            res = min(res,dp[i][j])
print(res if res != float('inf') else -1)

Measured memory_bytes: 76372
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
int a[maxn];
multiset<int> st;
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		if (st.size() == 0) {
			st.insert(a[i]);
		} else {
			multiset<int> ::iterator iter = st.lower_bound(a[i]);
			if (iter == st.begin()) {
				st.insert(a[i]);
			} else {
				iter--;
				st.erase(iter); st.insert(a[i]);
			}
		}
	}
	cout << st.size() << endl;
	return 0;
}


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

using namespace std;



int main(void){
    // Your code here!
    int N, A, B;
    int cnt = 0;
    cin >> N >> A >> B;       
    for(int i = 1; i <= N; i++){
        
        int i0,i1,i2,i3,i4;
        i0 = (i / 10000);
        i1 = (i % 10000) / 1000;
        i2 = (i % 1000) / 100;
        i3 = (i % 100) / 10;
        i4 = (i % 10);
        int sum = i0 + i1 + i2 + i3 + i4;

        if(A <= sum && sum <= B){
          //  cout << sum << endl;
          //  cout << i << endl;
            cnt += i;
        }
                
    }
    cout << cnt;
    
}




Measured memory_bytes: 256
def solve(N):
    M = 10**9+7
    DP = [0 for _ in range(N+1)]
    DP[0] = 1
    for n in range(N+1):
        for i in range(3,n+1):
            DP[n] += DP[n-i]
            DP[n] %= M

    return DP[N]

def main():
    S = int(input())
    print(solve(S))

if __name__ == "__main__":
    main()


Measured memory_bytes: 9200
macro_rules! input {
    // ?
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };

    // stdinの生成 値の読み込み開始
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    // ?
    ($next:expr) => {};
    // ?
    ($next:expr, ) => {};

    // 変数名:型の読み込みの繰り返し
    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    // 値を読み込むベース 型,の繰り返し
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    // 配列の読み込み
    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    // 文字列Vec<char>の読み込み
    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    // usize1?の読み込み
    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    // 指定した型で読み込み
    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}
fn main() {
    input! {
        nums: [usize;2],
    };

    println!("{}", solve(nums[0], nums[1]));
}

fn solve(a: usize, b: usize) -> usize {
    if a % b == 0 {
        return 0;
    } else {
        return 1;
    }
}

macro_rules! tests {
    ($($name:ident:[$( $args:expr ),*] => $output:expr,)*) => {
        mod tests {
            $(
                #[test]
                fn $name() {
                    assert_eq!($output,super::solve($($args),*));
                }
            )*
        }
    }
}


tests! {
    //テスト名:[引数]=>expected
    test1:[7,3]=>1,
    test2:[100,10]=>0,
    test3:[1,1]=>0,
}


Measured memory_bytes: 4352
//ABC100-D(Patisserie ABC)
#include<iostream>
using namespace std;

const long long INF=(1LL<<60);
//(綺麗さの合計の絶対値) + (おいしさの合計の絶対値) + (人気度の合計の絶対値) が最大になるように選ぶ
int N,M;
long long X[1010],Y[1010],Z[1010];
long long dp[1010][1010];
//dp[i][j]:i番目まででj個取ったときの得点の最大値
//求めたい値は、dp[N][M]について、それぞれのmax,*=-1したうえでのmaxを足して8通り

int main(){
    cin>>N>>M;
    for(int i=0; i<N; i++){
        cin>>X[i]>>Y[i]>>Z[i];
    }

    long long ans=-INF;
    
    for(int a=-1; a<2; a+=2){
        for(int b=-1; b<2; b+=2){
            for(int c=-1; c<2; c+=2){
                
                for(int i=0; i<N+1; i++)
                    for(int j=0; j<M+1; j++)dp[i][j]=-INF;

                dp[0][0]=0;

                for(int i=0; i<N; i++){
                    for(int j=0; j<M+1; j++){
                        //商品を追加するときの、値の合計の変化をdとおく
                        long long d=a*X[i]+b*Y[i]+c*Z[i];
                        dp[i+1][j]=max(dp[i+1][j],dp[i][j]);//商品を追加しないとき
                        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+d);//追加するとき
                    }
                }
                ans=max(ans,dp[N][M]);
            }
        }
    }
    cout<<ans<<endl;
    
    return 0;
}

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

int tax(int x, int p){
    return p * (100 + x) / 100;
}

int main(){
    int x, y, s;
    while(cin >> x >> y >> s, x != 0){
        int ans = 0;
        for(int a=1;a<s;++a){
            for(int b=1;b<s;++b){
                if(tax(x, a) + tax(x, b) == s){
                    ans = max(ans, tax(y, a) + tax(y, b));
                }
            }
        }
        cout << ans << endl;
    }

    return 0;
}


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

const int N = 4;
int cou[N];

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

	for (int i = 0; i < 3; ++i) {
		int a, b;
		cin >> a >> b;
		--a; --b;
		++cou[a];
		++cou[b];
	}
	int ones = 0;
	int twos = 0;
	for (int i = 0; i < 4; ++i) {
		if (cou[i] == 1) ++ones;
		if (cou[i] == 2) ++twos;
	}
	if (ones == 2 && twos == 2) cout << "YES\n";
	else cout << "NO\n";
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
int main(){
ll i,j,n,no,x,y,z;
string s;
cin>>s;
x=0;
for(i=0;i<2;i++){
	if(s[i]==s[i+1] && s[i]==s[i+2])
	{x=1;break;
}}
if(x==1)
cout<<"Yes"<<endl;
else cout<<"No"<<endl;

return 0;}



Measured memory_bytes: 256
def main():
    a, b = input().split()
    a = int(a)
    b_1 = ''
    b_1 += b[0]
    b_1 += b[2:]
    b_1 = int(b_1)

    answer = (a * b_1) // 100
    print(answer)


if __name__ == '__main__':
    main()

Measured memory_bytes: 9160
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;
 
const ll dx[4] = {1, 0, -1, 0};
const ll dy[4] = {0, 1, 0, -1};
 
int main() {
    ll h, w;
    cin >> h >> w;
    
    vector<string> board(h);
    rep(i, h) {
        cin >> board[i];
    }

    ll ans = h*w;
    rep(i, h) {
        rep(j, w) {
            if(board[i][j] == '#') {
                ans--;
            }
        }
    }

    vvl dist(h, vl(w, -1));  // dist[i][j] : (sx, sy)から(i, j)への最短距離(未訪問のとき-1)
    queue<P> Q;
    const ll sx = 0, sy = 0;
    Q.push(make_pair(sx, sy));
    dist[sx][sy] = 1;
    while(!Q.empty()) {
        ll x = Q.front().first;
        ll y = Q.front().second;
        rep(dir, 4) {
            ll nx = x + dx[dir];
            ll ny = y + dy[dir];
            if(nx < 0 || h <= nx || ny < 0 || w <= ny) {
                continue;
            }
            if(board[nx][ny] == '#') {
                continue;
            }
            if(0 <= dist[nx][ny]) {
                continue;
            }
            dist[nx][ny] = dist[x][y] + 1;
            Q.push(make_pair(nx, ny));
        }
        Q.pop();
    }
    
    if(dist[h-1][w-1] == -1) {
        out(-1);
    }
    else {
        ans -= dist[h-1][w-1];
        out(ans);
    }
    
    re0;
}

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

using namespace std;

#define int long long
#define pb push_back
#define fi first
#define se second
typedef pair<int, int> ii;
typedef pair<int, ii> iii;

const int N = 1e5 + 5;
int n, a[N], b[N], sumA, sumB, ans = 1e18, pos[2][N];
vector<iii> vec;

signed main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i] >> b[i], sumA += a[i], sumB += b[i];
        vec.pb(iii(a[i], ii(i, 0) ) );
        vec.pb(iii(b[i], ii(i, 1) ) );
    }
    sort(vec.begin(), vec.end() );

    int sum = 0;
    for (int i = 0; i < vec.size(); ++i) {
        if (i < n - 2) sum += vec[i].fi;
        pos[ vec[i].se.se ][ vec[i].se.fi ] = i;
    }

    for (int i = 1; i <= n; ++i) {
        if (pos[0][i] < n && pos[1][i] < n) ans = min(ans, sum + vec[n - 2].fi + vec[n - 1].fi);
        else if (pos[0][i] < n && pos[1][i] >= n) ans = min(ans, sum + vec[n - 2 + (pos[0][i] == n - 1)].fi + b[i]);
        else if (pos[1][i] < n && pos[0][i] >= n) ans = min(ans, sum + vec[n - 2 + (pos[1][i] == n - 1)].fi + a[i]);
        else ans = min(ans, sum + a[i] + b[i]);
    }

    cout << min(ans, min(sumA, sumB) );

    return 0;
}


Measured memory_bytes: 9584
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)n; ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cout<<*i<<" "; cout<<endl; }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
int H, W;
int grid[11][11];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
string state = "UDLR";
int lim[4] = {1,0,3,2};
bool used[11][11];
string dfs(int x, int y, int s, int rem, string res){
  //printf("dfs:%d %d %d %d %s\n", x, y, s, rem, res.c_str());
  if(rem == 0){
    return res;
  }
  REP(r, 4)if(r != lim[s]){
    REP(p, 10){
      int nx = x + p * dx[r];
      int ny = y + p * dy[r];
      if(0 <= nx && 0 <= ny && nx < W && ny < H && !used[ny][nx] && grid[ny][nx]){
        used[ny][nx] = true;
        //printf("call %d %d %d %d %s\n", nx, ny, r, rem -1, (res+state[r]).c_str());
        string response = dfs(nx, ny, r, rem-1, res+state[r]);
        used[ny][nx] = false;
        if(response != "") return response;
        break;
      }
    }
  }
  return "";
}

int main(){
  while(cin>>H>>W && H){
    int nx, ny, s;
    int cnt = 0;
    REP(y, H){
      string t; cin>>t;
      REP(x, W){
        if(t[x] == 'o'){
          grid[y][x] = 1;
          cnt += 1;
        }else if(t[x] == '.'){
          grid[y][x] = 0;
        }else{
          grid[y][x] = 0;
          nx = x;
          ny = y;
          REP(i, 4)if(state[i] == t[x])s = i;
        }
      }
    }
    memset(used, 0, sizeof(used));
    string ans = dfs(nx, ny, s, cnt, "");
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 0
/*

*/
#include<iostream>
#include<iomanip>
#include<ios>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<algorithm>
#include<utility>
#include<math.h>
#include<cstdlib>
#define rep(i, n) for(int i=0;i<n;i++)
#define repb(i, a, b) for(int i=a;i<b;i++)
#define MAX_N 10000

using namespace std;
typedef pair<int, int> P;
typedef long long int ll;

const int INF = 1<<30;
const ll MOD = ll(1e9+7);

int main(){
  map<P, int> mp;
  int h, w, n;cin>>h>>w>>n;
  rep(i, n){
    int a, b;cin>>a>>b;a--;b--;
    repb(i, -1, 2){
      repb(j, -1, 2){
        if(a+i>=1&&a+i<h-1&&b+j>=1&&b+j<w-1)mp[P(a+i, b+j)]++;
      }
    }
  }
  vector<int> cnt(10, 0);
  ll sum=ll(h-2)*(w-2);
  for(auto itr=mp.begin();itr!=mp.end();itr++){
    cnt[itr->second]++;
    sum--;
  }
  cout<<sum<<endl;
  repb(i, 1, 10){
    cout<<cnt[i]<<endl;
  }
  // system("read -n 1 -s -p \"Press any key to continue...\"");
}


Measured memory_bytes: 56448
#![allow(dead_code)]

use std::io::{stdin, Read};

const MOD: u64 = 1000000007;

fn gcd(a: u64, b: u64) -> u64 {
    match b {
        0 => a,
        _ => gcd(b, a % b),
    }
}

fn powmod(base: u64, exp: u64, m: u64) -> u64 {
    let b: Vec<bool> = format!("{:b}", exp)
        .chars()
        .map(|x| x.to_digit(10).unwrap() != 0)
        .collect();
    let mut v = 1;
    for bi in b {
        v *= v;
        v %= m;
        if bi {
            v *= base;
            v %= m
        }
    }
    return v % m;
}

fn invmod(x: u64, m: u64) -> u64 {
    powmod(x, m - 2, m)
}

fn prime_factors(x: u64) -> Vec<u64> {
    let mut res = vec![];
    let mut y = x;
    let mut p = 2;
    let upper = (y as f64).sqrt() as u64;
    while y > 1 && p <= upper {
        match y % p {
            0 => {
                res.push(p);
                y /= p;
            }
            _ => {
                p += 1;
            }
        }
    }
    if y > 1 {
        res.push(y)
    }
    return res;
}

fn get_factorials(n: u64, m: u64) -> Vec<u64> {
    let mut res = vec![1];
    let mut cur = 1;
    for i in 1..(n + 1) {
        cur *= i;
        cur %= m;
        res.push(cur);
    }
    res
}

fn get_facinvs(n: u64, m: u64) -> Vec<u64> {
    let mut res = vec![1];
    let mut cur = 1;
    for i in 1..(n + 1) {
        cur *= invmod(i, m);
        cur %= m;
        res.push(cur);
    }
    res
}

fn combmod(a: u64, b: u64, m: u64, facts: &Vec<u64>, invs: &Vec<u64>) -> u64 {
    if a < b {
        0
    } else {
        (((facts[a as usize] * invs[b as usize]) % m) * invs[(a - b) as usize]) % m
    }
}

macro_rules! parse {
    ($iter: ident) => {
        $iter.next().unwrap().parse().unwrap()
    };
    ($iter: ident,2) => {
        (parse!($iter), parse!($iter))
    };
    ($iter: ident,3) => {
        (parse!($iter), parse!($iter), parse!($iter))
    };
    ($iter: ident,4) => {
        (parse!($iter), parse!($iter), parse!($iter), parse!($iter))
    };
    ($iter: ident, $n: ident) => {
        $iter.take($n).map(|e| e.parse().unwrap()).collect();
    };
}

fn solve(x: u64, y: u64, c: u64) -> u64 {
    (1..x)
        .map(|d| (d * ((((((x - d) * y) % MOD) * y) % MOD) * c) % MOD) % MOD)
        .fold(0, |a, b| (a + b) % MOD)
}

fn main() {
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    let mut iter = s.split_whitespace();
    let (n, m, k): (u64, u64, u64) = parse!(iter, 3);

    let facts = get_factorials(200001, MOD);
    let invs = get_facinvs(200001, MOD);
    let c = combmod(n * m - 2, k - 2, MOD, &facts, &invs);
    let mut res = solve(n, m, c) + solve(m, n, c);
    res %= MOD;
    println!("{}", res)
}


Measured memory_bytes: 10492
import java.io.*;
import java.util.*;

import static java.lang.Math.*;

public class Main {
    static public class pair {
        int u;
        int idx;
        int val;

        public pair(int x, int i) {
            u = x;
            idx = i;
            val = -1;
        }
    }



    static ArrayList<pair>[] adj;
    static int[] Arr, Arry;
    static int inf = (int) 1e9,n;
    static boolean[][] matrix;
    static long[][] memo;
    static long mod = 998244353;

    public static void main(String[] args) throws Exception {

        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        long a=sc.nextLong();
        long b=sc.nextLong();
        long c=sc.nextLong();
        long part1=4*a*b;
        long part2=c-a-b;
        part2*=part2;

        if(part1<part2&&c>a+b)
            pw.println("Yes");
        else
            pw.println("No");
        pw.close();
    }

    public static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public Scanner(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(s));

        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

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

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

        public String nextLine() throws IOException {
            return br.readLine();
        }

        public double nextDouble() throws IOException {
            String x = next();
            StringBuilder sb = new StringBuilder("0");
            double res = 0, f = 1;
            boolean dec = false, neg = false;
            int start = 0;
            if (x.charAt(0) == '-') {
                neg = true;
                start++;
            }
            for (int i = start; i < x.length(); i++)
                if (x.charAt(i) == '.') {
                    res = Long.parseLong(sb.toString());
                    sb = new StringBuilder("0");
                    dec = true;
                } else {
                    sb.append(x.charAt(i));
                    if (dec)
                        f *= 10;
                }
            res += Long.parseLong(sb.toString()) / f;
            return res * (neg ? -1 : 1);
        }

        public boolean ready() throws IOException, IOException {
            return br.ready();
        }

    }
}


Measured memory_bytes: 22612
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <sstream>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(c) (c).begin(), (c).end()
#define loop(i,a,b) for(ll i=a; i<ll(b); i++)
#define rep(i,b) loop(i,0,b)
#ifdef DEBUG
#define dump(...) (cerr<<#__VA_ARGS__<<" = "<<(DUMP(),__VA_ARGS__).str()<<" ["<<__LINE__<<"]"<<endl)
struct DUMP:ostringstream{template<class T>DUMP &operator,(const T&t){if(this->tellp())*this<<", ";*this<<t;return *this;}};
#else
#define dump(...)
#endif

const int MAX_N=50100;
int p[(MAX_N+1)/2];
bool isp[MAX_N+1];

int gen_ps(){
    memset(isp,1,sizeof(isp));
    isp[0]=isp[1]=false;
    int idx=0;
    loop(i,2,MAX_N+1){
        if(!isp[i]) continue;
        p[idx++]=i;
        for(int j=i+i; j<=MAX_N; j+=i){
            isp[j]=false;
        }
    }
    return idx;
}

int main(){
    ll a,b;
    while(cin>>a>>b && a){
        ll g = __gcd(a,b);
        cout << g << " " << a/g*b << endl;
    }
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD 1000000007
#define ff first
#define ss second
#define pb push_back
#define N 100005

ll inv[N], fac[N], finv[N];

void make()
{
	fac[0] = fac[1] = 1;
	inv[1] = 1;
	finv[1] = finv[0] = 1;
	for(int i = 2; i < N; ++i)
	{
		fac[i] = i * fac[i - 1] % MOD;
		inv[i] = MOD - MOD/i * inv[MOD % i] % MOD;
		finv[i] = inv[i] * finv[i - 1] % MOD;
	}
}

ll C(ll n, ll k)
{
	if(n < k || n < 0) return 0;
	return fac[n] * finv[n - k] % MOD* finv[k] % MOD;
}

ll gcd(ll a, ll b)
{
	if(b == 0)
		return a;
	return gcd(b, a % b);
}
#define N 100005
int n, k;
int wv[110][2];
ll dp[110][N];
ll dpf(int i, int w)
{
	if(w < 0)
		return -1e12;
	if(w == 0 || i == n)
		return 0;
	if(dp[i][w] >= 0)
	{
		return dp[i][w];
	}

	return dp[i][w] = max(wv[i][1] + dpf(i + 1, w - wv[i][0]), dpf(i + 1, w));
}

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

	cin >> n >> k;
	for (int i = 0; i < n; ++i)
	{
		cin >> wv[i][0] >> wv[i][1];
		for (int j = 0; j <= k; ++j)
		{
			dp[i][j] = -1;
		}
	}
	ll ans = dpf(0, k);
	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 82176
import sys
input = sys.stdin.readline

class FenwickTree:
    def __init__(self, n: int) -> None:
        self._n = n
        self.data = [0] * n

    def add(self, p: int, x) -> None:
        assert 0 <= p < self._n
        p += 1
        while p <= self._n:
            self.data[p - 1] += x
            p += p & -p

    def __sum__(self, r: int):
        s = 0
        while r > 0:
            s += self.data[r - 1]
            r -= r & -r
        return s

    def sum(self, l: int, r: int):
        assert 0 <= l <= r <= self._n
        return self.__sum__(r) - self.__sum__(l)


n, q = map(int, input().split())

fw = FenwickTree(n)
for index, i in enumerate(map(int, input().split())):
    fw.add(index, i)

for _ in range(q):
    t, p, x = map(int, input().split())
    if t == 0:
        fw.add(p, x)
    else:
        print(fw.sum(p, x))

Measured memory_bytes: 120332
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <set>
#include <map>
#include <utility>
#include <string>
#include <sstream>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cassert>
#include <climits>

int64_t kRem = 1000000007;

using namespace std;

// NG ケース一覧
enum Char {
	A,
	G,
	C,
	T
};

bool is_ok(int val[4])
{
	// NG ケースは A_GC, AG_C, GAC, ACG, AGC
	if (val[0] == A && val[2] == G && val[3] == C) return false;
	if (val[0] == A && val[1] == G && val[3] == C) return false;
	if (val[0] == G && val[1] == A && val[2] == C) return false;
	if (val[1] == G && val[2] == A && val[3] == C) return false;
	if (val[0] == A && val[1] == C && val[2] == G) return false;
	if (val[1] == A && val[2] == C && val[3] == G) return false;
	if (val[0] == A && val[1] == G && val[2] == C) return false;
	if (val[1] == A && val[2] == G && val[3] == C) return false;

	return true;
}

void dp_progress(vector<uint64_t[4][4][4]>& dp, int i, int j, int k, int m)
{
	uint64_t val = 0;
	for (int h = 0; h < 4; h++) {
		int sel[4] = { h, i, j, k };
		if (!is_ok(sel)) continue;

		val += dp[m-1][h][i][j];
	}

	dp[m][i][j][k] = val % kRem;
}

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

	// 4 次元 DP
	vector<uint64_t[4][4][4]> dp(n + 1); // 1 origin
	
	// 初期化
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			for (int k = 0; k < 4; k++) {
				dp[3][i][j][k] = 1;
			}
		}
	}
	// AGC, GAC, ACG のみ不可
	dp[3][A][G][C] = 0;
	dp[3][G][A][C] = 0;
	dp[3][A][C][G] = 0;

	// 4 - n DP
	for (int m = 4; m <= n; m++) {
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				for (int k = 0; k < 4; k++) {
					dp_progress(dp, i, j, k, m);
				}
			}
		}
	}

	// 最終結果
	uint64_t val = 0;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			for (int k = 0; k < 4; k++) {
				val += dp[n][i][j][k];
			}
		}
	}
	cout << (val %= kRem) << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <functional>
#include <string>
#include <cstdlib>
#include <numeric>
#include <cstdbool>
#include <map> 
#include<set>
#include<queue>

typedef long long ll;


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

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

const long long INF = 1000000000000000;
const ll inf = -1e18;
typedef pair<int, int> P;
ll ma = 1000000000 + 7;
ll h, w, n,k; string s;
char maze[60][60];
int dis[101][101];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
ll dp[100010][2];
int gcd(int x, int y) {
	if (x % y == 0) return y;
	return gcd(y, x % y);

}
int main() {
	cin >> n; int res = 0;
	for (int i = 105; i <= n; i+=2) {
		int cnt = 0;
		for (int j = 1; j <= i; j++) {
			if (i % j == 0) {
				cnt++;
			}
		}
		if (cnt == 8) {
			res++;
		}
	}
	cout << res << endl;
}




Measured memory_bytes: 256