akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
/*
    s.find_by_order(k) ---> returns iterator to the element at index(from 0) k
    s.order_of_key(val) ---> number of elements that are strictly smaller than the given value
*/
typedef long long int ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<long long int> vl;
typedef vector<vector<int>> vvi;
typedef vector<vector<long long int>> vvl;
typedef pair<int, int> pii;
typedef pair<long long int, long long int> pll;
typedef vector<pair<int, int>> vii;
typedef vector<pair<long long int, long long int>> vll;
#define fastIO() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define test() long long int tc; cin >> tc; cin.ignore(); while(tc--) 
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mp make_pair
#define MOD 1000000007
#define SMOD 998244353
#define HASH 18014398241046527
#define pq priority_queue
#define all(x) x.begin(),x.end()
#define SP(x) setprecision(x)
#define sp " "
#define inp(a) ll a;cin>>a;cin.ignore()
#define inps(a,b) ll a,b;cin>>a>>b;cin.ignore()
#define out(a) cout<<SP(20)<<a<<'\n'
#define outs(a,b) cout<<SP(20)<<a<<" "<<b<<'\n'
#define ins insert
#define er erase
#define lb lower_bound
#define ub upper_bound
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
#define inpa(a,n) ll a[n]; for(int i=0; i<n; i++){cin>>a[i];}
#define inpv(a,n) vl a; for(int i=0; i<n; i++){inp(x);a.pb(x);}
#define outa(a,n) for(int i=0;i<n;i++){cout<<a[i]<<" ";}cout<<'\n';
#define outv(v) for(auto i:v){cout<<i<<" ";}cout<<'\n';
set<char> vow = {'a','e','i','o','u','A','E','I','O','U'};
ll xpow(ll n, ll m){if(m==0){return 1;}else{ll x = xpow(n, m/2);if(m&1){return x*x*n;}else{return x*x;}}}
ll xmod(ll a, ll m){return (((a%m)+m)%m);}
ll xmodpow(ll n, ll m, ll y){if(m==0){return 1;}else{ll x = xmodpow(n, m/2, y);if(m&1){return xmod((xmod((xmod(x,y)*xmod(x,y)),y)*xmod(n,y)),y);}else{return xmod((xmod(x,y)*xmod(x,y)),y);}}}

ll dx[] = {1, 0, -1, 0};
ll dy[] = {0, 1, 0, -1};





void SOLVE(){
    ll x;
    cin >> x;
    for(ll i=1; ; i++){
        ll y = i*x;
        if(y%360==0){
            cout << i << '\n';
            return;
        }
    }
}

int main() {
	fastIO();
	// #ifndef ONLINE_JUDGE
    //     freopen("i.txt", "r", stdin);
    //     freopen("o.txt", "w", stdout);
	// #endif

    ll TC = 1;
    // cin >> TC;
    for(ll tc1=1; tc1<=TC; tc1++){
        // cout << "Case #" << tc1 << ": ";
        SOLVE();
    }
    printclock;
}

Measured memory_bytes: 3848
#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
int main(void){
    double x1,x2,y1,y2;
    cin >> x1 >> y1 >> x2 >> y2 ;
    cout << fixed;
    cout << setprecision(5)<<sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)) <<endl;
}



Measured memory_bytes: 3280
import java.util.Scanner;
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();

        if(A<C && C<B){
        	System.out.println("Yes");
        }else if(B<C && C<A) {
        	System.out.println("Yes");
        }else {
        	System.out.println("No");
        }
    }
}

Measured memory_bytes: 21844
function main(input) {
  input = input.trim().split("\n");
  const n = Number(input[0]);
  const ss = input.slice(1);
  const map = {};
  for (let i = 0; i < n; i++) {
    const char = ss[i];
    const sortedChar = char.split("").sort().join("");
    if (!map[sortedChar]) {
      map[sortedChar] = 1;
      continue;
    }
    map[sortedChar]++;
  }
  let result = 0;
  Object.keys(map).forEach(key => {
    const num = map[key];
    if (num !== 1) {
      result += combination(num, 2);
    }
  });
  console.log(result);
}
function permutation(n, r) {
for(var i = 0, res = 1; i < r; i++) {
res *= n - i;
}
return res;
}

function combination(n, r) {
return permutation(n, r) / permutation(r, r);
}
main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 45668
#include<iostream>
#include<cstdio>

using namespace std;

int main(){
    int n;
    cin >> n;
    int A[n];
    for (int i = 0; i < n; i++) cin >> A[i];
    for (int a = 0; a < n; a++){
        cout << A[a];
        if (a == n-1) cout << endl;
        else cout << " ";
    }
    for (int i = 1; i < n; i++) {
        int v = A[i];
        int j = i-1;
        while (j >= 0 && A[j] > v){
            A[j+1] = A[j];
            j--;
        }
        A[j+1] = v;
        for (int a = 0; a < n; a++){
            cout << A[a];
            if (a == n-1) cout << endl;
            else cout << " ";
        }
    }
    return 0;
}


Measured memory_bytes: 3084
#include <iostream>
#include <map>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <climits>
#include <stack>
#include <queue>
#include <set>
#include <cctype>
#include <bitset>
#include <type_traits>

#include <list>
using namespace std;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define YES(j) cout << (j ? "YES" : "NO") << endl;
#define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
#define yes(j) std::cout << (j ? "yes" : "no") << endl;

int main(void)
{
    int h, a;
    int i = 0;
    cin >> h >> a;
    while (1)
    {
        if (h <= 0)
        {
            cout << i << endl;
            return 0;
        }
        h -= a;
        i++;
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int N =5;

int main(){
  vector<int> vec(N);
  for (int i = 0; i < N; i++) {
    cin >> vec.at(i);
  }
  for (int i = 0; i < N; i++) {
    if (vec.at(i)==0){
         cout << i+1 << endl;
    }
  }
}

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

int N;
vector<int> A, B, C;

int main()
{
  cin >> N;
  int a, b, c;
  for (int i = 0; i < N; i++)
  {
    cin >> a;
    A.push_back(a);
  }
  for (int i = 0; i < N; i++)
  {
    cin >> b;
    B.push_back(b);
  }
  for (int i = 0; i < N; i++)
  {
    cin >> c;
    C.push_back(c);
  }
  sort(A.begin(), A.end());
  sort(B.begin(), B.end());
  sort(C.begin(), C.end());
  long long ans = 0, tmp_AB, tmp_BC;
  for (int i = 0; i < N; i++)
  {
    b = B.at(i);
    tmp_AB = lower_bound(A.begin(), A.end(), b) - A.begin();
    tmp_BC = C.end() - upper_bound(C.begin(), C.end(), b);
    ans += tmp_AB * tmp_BC;
  }
  cout << ans << endl;
}


Measured memory_bytes: 1784
#include <stdio.h>
int main(void){
	int b1,b2,b3;
	scanf("%d %d %d",&b1,&b2,&b3);
	if(b1==1 && b2==1){
		printf("Open\n");
	}
	else if(b3==1){
		printf("Open\n");
	}
	else{
	printf("Close\n");}
	return 0;
}


Measured memory_bytes: 2104
#include<stdio.h>

int main(){
    int A, B, K, tmp;
    int ans=0, i, j;

    scanf("%d %d %d", &A, &B, &K);

    if(A<B){
        tmp = A;
        A = B;
        B = tmp;
    }

    for(i=B; i>0; i--){
        if((A%i + B%i) == 0){
            ans += 1;
        }
        if(ans == K){
            break;
        }
    }
    printf("%d", i);

    return 0;
}

Measured memory_bytes: 128
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


# aとbの最大公約数
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


# aとbの最小公倍数
def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def check(N, X):
    s = "P"
    for i in range(N):
        s = "B" + s + "P" + s + "B"
    return s[:X].count("P")


def func(N, X, P, B):
    if X == 0:
        return 0
    if N == 0:
        return 1

    num = P[N - 1] + B[N - 1]

    ans = 0
    X -= 1
    if X >= num:
        ans += P[N - 1]
        X -= num
    else:
        return func(N - 1, X, P, B)

    if X <= 0:
        return ans
    X -= 1
    ans += 1
    if X <= 0:
        return ans

    if X >= num:
        X -= num
        ans += P[N - 1]
    else:
        return ans + func(N - 1, X, P, B)

    X -= 1

    return ans


def solve(N, X):
    P = [0] * 51
    B = [0] * 51
    P[0] = 1
    for i in range(1, 51):
        P[i] = P[i - 1] * 2 + 1
        B[i] = B[i - 1] * 2 + 2

    return func(N, X, P, B)


def main():
    N, X = map(int, input().split())
    print(solve(N, X))


if __name__ == '__main__':
    main()


Measured memory_bytes: 3956
#!/usr/bin/env python
"""AtCoder Beginner Contest 168: A - ∴ (Therefore)
https://atcoder.jp/contests/abc168/tasks/abc168_a
"""


def main():
    N = input()

    v = int(N[-1]) % 10
    if v in {2, 4, 5, 7, 9}:
        print('hon')
    elif v in {0, 1, 6, 8}:
        print('pon')
    elif v in {3}:
        print('bon')


if __name__ == '__main__':
    main()


Measured memory_bytes: 9104
using System;
using System.Linq;
using System.Collections.Generic;
public class Hello{
    public static void Main(){
        var input = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
        var a = input[0];
        var b = input[1];
        var ans = 0L;
        if(a == b){
            ans = 2 * f(a) * f(b);
        }else if(Math.Abs(a - b) == 1){
            ans = f(a) * f(b);
        }
        
        Console.WriteLine(ans % 1000000007);
    }
    
    static long f(long n){
        long x = 1L;
        for(var i = 1L;i <= n;i++){
            x *= i;
            x %= 1000000007;
        }
        return x;
    }
}


Measured memory_bytes: 13396
#include<bits/stdc++.h>
#define MAX 1000001
using namespace std;
void frac_init(vector<int> &frac){
    int n[MAX];
    for(int i=0; i<MAX; i++){
        n[i]=1;
    }
    for(int num=2; num<MAX; num++){
        if(n[num]==1){
            frac.push_back(num);
            for(int i=num; i<MAX; i+=num){
                n[i]=0;
            }
        }
    }
}
int main(){
    long long N,Norig;
    int stack[41];
    int f,e,ans=0;
    vector<int> frac;
    frac_init(frac);
    stack[0]=0;
    for(int i=0; i<9; i++){
        for(int j=(i*(i+1))/2; j<((i+1)*(i+2))/2; j++){
            if(j>40) break;
            stack[j]=i;
        }
    }
    cin >> N;
    for(int i=0; i<frac.size(); i++){
        f=frac.at(i);
        e=0;
        while(N%f==0){
            N/=f;
            e++;
        }
        ans+=stack[e];
        if(N==1) break;
    }
    if(N>1) ans++;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 7652
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k,ans,tot,cnt,a[200001],b[200001];
signed main()
{
	scanf("%lld%lld%lld",&n,&m,&k);
	for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    for(int i=1;i<=m;i++)
    {
        scanf("%lld",&b[i]);
        tot+=b[i];
    }
    cnt=m;
    for(int i=0;i<=n;i++)
    {
    	tot+=a[i];
    	while(tot>k&&cnt>0)
        {
    		tot-=b[cnt];
            cnt--;
        }
    	if(tot>k)
    		break;
    	ans=max(ans,cnt+i);
	}
	cout<<ans;
	return 0;
}


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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define deg_to_rad(deg) (((deg) / 360) * 2 * M_PI)
#define rad_to_deg(rad) (((rad) / 2 / M_PI) * 360)

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

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

typedef long long ll;

const string YES = "Yes";
const string NO  = "No";

void solve(std::string S, std::string T) {
    string ans = YES;
    rep(i, S.size()) {
        if (S[i] != T[i])
            ans = NO;
    }
    cout << ans << endl;
}

int main() {
    std::string S;
    std::cin >> S;
    std::string T;
    std::cin >> T;
    solve(S, T);
    return 0;
}


Measured memory_bytes: 3628
#include<iostream>

using namespace std;

#define ll long long int

ll dp[(int)1e5 + 1];

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

	int n,w; cin >> n >> w;
	int weight[n],values[n];

	int limit = 0;

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

	for(int i = 0; i < n; i++) {
		for(int j = w; j >= weight[i]; j--) {
			dp[j] = max(dp[j],dp[j-weight[i]] + values[i]);
		}
	}

	cout << dp[w] << '\n';

	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define endl              "\n"
#define pb              push_back
#define fir               first
#define sec               second
#define all(v)            ((v).begin()), ((v).end())
#define sz(v)            ((int)((v).size()))
#define ll              long long
#define ld              long double
#define lp(i, n)        for(int i = 0 ; (int)i<n ; i++)
#define loop(i, x, n)       for(int i=x ; (int)i<=n ; i++)
#define isPowerOfTwo(s) (!(s & (s-1)))
typedef vector<int> vi;
typedef deque<int> de;
void origi() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
}
map<string, int>m1;
map<int,string>m2;
void tiranga() {
    int n;
    string s;
    cin >> n;
    lp(i, n) {
        cin >> s;
        m1[s]++;
    }
    int Max = INT_MIN;
    for (auto mm:m1)
        Max = max(Max, mm.second);
    for(auto mm:m1){
        if (mm.second == Max)
            cout << mm.first << endl;
    }

}
int main() {
#ifndef ONLINE_JUDGE
    //freopen("input.txt", "r", stdin);
#else
#endif 
    origi();
    tiranga();
    //cout << sumOfDig(123654);
   // genLarge(10, 10);
   // genSmall(10);
   
}


Measured memory_bytes: 23808
#include<stdio.h>

int a[1000000],n;
int bs(int key);

int main(void){
	int i,q,k,sum=0;
	
	scanf("%d",&n);
	for(i=0;i<n;i++)scanf("%d",&a[i]);
	
	scanf("%d",&q);
	for(i=0;i<q;i++){
		scanf("%d",&k);
		if(bs(k))sum++;
	}
	printf("%d\n",sum);
	
	return 0;
}

int bs(int key){
	int left=0;
	int right=n;
	int mid;
	while(left<right){
		mid=(left+right)/2;
		if(key==a[mid])return 1;
		if(key>a[mid])left=mid+1;
		else if(key<a[mid])right=mid;
	}
	return 0;
}


Measured memory_bytes: 2180
#include <iostream>
using namespace std;
int main()
{
	string s;
	string x = "SUN";
	string y = "MON";
	string z = "TUE";
	string a = "WED";
	string b = "THU";
	string c = "FRI";
	string d = "SAT";
	cin >> s;
	for (int i = 0; i < s.length(); i++) {
		if (s[i] == x[i] && s[i + 1] == x[i + 1] && s[i + 2] == x[i + 2]) {
			cout << 7;
			break;
		}
		else if (s[i] == y[i] && s[i + 1] == y[i + 1] && s[i + 2] == y[i + 2]) {
			cout << 6;
			break;
		}
		else if (s[i] == z[i] && s[i + 1] == z[i + 1] && s[i + 2] == z[i + 2]) {
			cout << 5;
			break;
		}
		else if (s[i] == a[i] && s[i + 1] == a[i + 1] && s[i + 2] == a[i + 2]) {
			cout << 4;
			break;
		}
		else if (s[i] == b[i] && s[i + 1] == b[i + 1] && s[i + 2] == b[i + 2]) {
			cout << 3;
			break;
		}
		else if (s[i] == c[i] && s[i + 1] == c[i + 1] && s[i + 2] == c[i + 2]) {
			cout << 2;
			break;
		}
		else if (s[i] == d[i] && s[i + 1] == d[i + 1] && s[i + 2] == d[i + 2]) {
			cout << 1;
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static void main(String[] args){

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int X = sc.nextInt();
		int T = sc.nextInt();
      
      if(N<=X){
		System.out.println(T);
		return;
       }
      
		int times = (int) Math.floor(N/X);
      
       if(N%X!=0){
		times++;
       }
		System.out.println(T*times);
		return;
	}

}


Measured memory_bytes: 35652
import java.util.Scanner;
public class Main {
    public static void main (String[] args) {
	Scanner scan = new Scanner(System.in);
	int n = 4;
	int[] a = new int[n];
	int[] b = new int[n];
	int hit, blow;
	String[] inputA, inputB;
	while (scan.hasNext()) {
	    inputA = scan.nextLine().split(" ");
	    inputB = scan.nextLine().split(" ");
	    for (int i = 0; i < n; i++) {
		a[i] = Integer.parseInt(inputA[i]);
		b[i] = Integer.parseInt(inputB[i]);
	    }
	    hit = 0;
	    blow = 0;
	    for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
		    if (b[i] == a[j]) {
			if (i ==j) {
			    hit++;
			} else {
			    blow++;
			}
		    }
		}
	    }
	    System.out.println(hit + " " + blow);
	}
    }
}

Measured memory_bytes: 26112
import { readFileSync } from "fs";

const read = () =>
  readFileSync(0, "utf8")
    .split("\n")
    .map((line) => line.split(" "));

const main = (input: string[][]) => {
  const [, T] = input[0].map(Number);
  const routes = input.slice(1).map((line) => line.map(Number));

  let min = Infinity;

  routes.forEach(([c, t]) => {
    if (t <= T && c < min) {
      min = c;
    }
  });

  return min === Infinity ? "TLE" : min;
};

console.log(main(read()));


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

int main() {
  int n;
  string s;
  cin >> n >> s;
  
  int ans = 0;
  int k = 0;
  for(int i = 0; i < n; i++){
    if(s.at(i) == 'I') k++;
    if(s.at(i) == 'D') k--;
    ans = max(ans, k);
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 256
n=int(input())
s=input()
sb=[0]*n
sw=[0]*n
wb=[]
for i in range(n-1):
    if s[i:i+2]==".#":
        wb.append(i)
for i in range(n):
    if s[i]==".":
        if i==0:
            sw[i]=1
        else:
            sw[i]=1+sw[i-1]
            sb[i]=sb[i-1]
    else:
        if i==0:
            sb[i]=1
        else:
            sb[i]=1+sb[i-1]
            sw[i]=sw[i-1]
anses=[len([x for x in s if x=="#"]),len([x for x in s if x=="."])]
for i in wb:
    anses.append(sb[i]+sw[n-1]-sw[i])
print(min(anses))

Measured memory_bytes: 56672
def prime(n):
  prime_table = [2]
  for i in range(3,n+1):
    f = 1
    for j in prime_table[:bisect.bisect_right(prime_table,int(i**0.5))]:
      if i % j == 0:
        f = 0
        break
    if f:
      prime_table.append(i)
  return prime_table

import bisect
x = int(input())
pt = prime(5*10**5)
print(pt[bisect.bisect_left(pt,x)])

Measured memory_bytes: 4840
X = int(input())

def primes(n):
    sieve = [True] * n
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)
    return [2] + [i for i in range(3,n,2) if sieve[i]]

pn = primes(10**6)

def bsearch(v, l, r):
    if l >= r - 1:
        return [l, r]
    m = l + ((r - l) // 2)
    if pn[m] < v:
        return bsearch(v, m, r)
    else:
        return bsearch(v, l, m)

l, r = bsearch(X, 0, len(pn))

if X == 2:
    print(2)
else:
    print(pn[r])


Measured memory_bytes: 14856
import java.util.Scanner;
  class Main{
    public static void main(String[] args){
    	Scanner cin = new Scanner(System.in);
    	while(cin.hasNext()){
    		long a = cin.nextInt();
    		long b = cin.nextInt();
    		long m = a;
    		long n = b;
    		long p = m;
    		while(n != 0){
    			p = n; n = m%n; m = p;
    		}
    		System.out.println(m+" "+a*b/m);
    	}
    }
}

Measured memory_bytes: 17220
#include<iostream>
#include<limits.h>
#include<cmath>
using namespace std;

int main(){
	int n, l;
	cin >> n >> l;
	double sum = 0;
	for(int i=1;i<=n;i++){
		sum += l+i-1;
	}
	int apple=0;
	int tmp_min = INT_MAX;
	double mean_all = sum;
	double mean_but1;
	for(int i = 1;i<=n;i++){
		mean_but1=(sum-(l+i-1));
		if(abs(mean_all-mean_but1) < tmp_min){
			tmp_min = abs(mean_all-mean_but1);
			apple = i;
		}
	}
	cout << sum-(l+apple-1) << endl;
	return 0;
}


Measured memory_bytes: 256
#!/usr/bin/ python3.8
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import itertools
H, W, K = map(int, readline().split())
S = [list(map(int, line.rstrip().decode())) for line in readlines()]
# transpose
S = tuple(itertools.chain(*zip(*S)))

INF = 10 ** 9


def solve(s):
    dp = list(S)
    for j in range(H - 1):
        if s & (1 << j):
            for n in range(0, H * W, H):
                dp[n + j + 1] += dp[n + j]
    cut = H - 1 - bin(s).count('1')
    for n in range(0, H * W, H):
        if any(dp[n + i] > K for i in range(H)):
            return INF
        if n + H == H * W:
            return cut
        if any(dp[n + i] + dp[n + i + H] > K for i in range(H)):
            cut += 1
            continue
        for i in range(H):
            dp[n + i + H] += dp[n + i]
    return cut


answer = min(solve(s) for s in range(1 << (H - 1)))
print(answer)


Measured memory_bytes: 56668
#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
cout.tie(0);
cin.tie(NULL);
    long h,s=0;
    cin>>h;
    if(h==1)
    {
    s=1;
    cout<<s;
    return 0;
    }
    else
    {
        h/=2;
        s=1;
    }
    int i=1;
    while(h)
    {
    h/=2;
    s+=pow(2,i);
    i++;
    }
    cout<<s;
}


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

using namespace std;

int n, a;
set< long > m;

int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a;
        if(m.find(a) == m.end())
            m.insert(a);else{
                cout << "NO";
                return 0;
            }
    }
    cout << "YES";
    return 0;
}


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

int main() {
  int N,Q;
long long C;
C=0;
  cin>>N;
int A[N],B[40001],D[40001];
for(int i=0;i<N;i++){
cin>>A[i];
}
for(int i=0;i<40001;i++){
B[i]=0;
  D[i]=0;
}
B[0]=1;
cin>>Q;
int M[Q];
for(int i=0;i<Q;i++){
cin>>M[i];
}
for(int i=0;i<N;i++){
C+=A[i];
for(int j=0;j<C;j++){
if(B[j]==1){
D[j+A[i]]=1;
}
}
  for(int j=0;j<=C;j++){
    if(B[j]==1||D[j]==1){
      B[j]=1;
    }
    D[j]=0;
  }
}
 for(int i=0;i<Q;i++){
if(B[M[i]]==1){
  cout <<"yes"<< endl;
}
else{
  cout <<"no"<< endl;
}
}
}



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

const long long BIG = 10000000000;

long long solve(int N, int W, int w[], int v[]){
  const int V = 1000 * N;
  long long sumw[V + 1];
  long long sumwp[V + 1];
  
  fill(sumw, sumw + V + 1, BIG);
  fill(sumwp, sumwp + V + 1, BIG);
  
  sumw[0] = sumwp[0] = 0;
  
  for(int i = 0; i < N; ++i){
    for(int j = v[i]; j <= V; ++j){
      sumw[j] = min(sumwp[j-v[i]] + w[i], sumw[j]);
    }
    copy(sumw, sumw + V + 1, sumwp);
  }
  
  long long ans = 0;
  for(int j = 0; j <= V; ++j){
    if(sumw[j] <= W){
      ans = j;
    }
  }
  
  return ans;
}


int main(){
  int N, W;
  cin >> N >> W;
  int w[N], v[N];
  for(int i = 0; i < N; ++i){
    cin >> w[i] >> v[i];
  }
  cout << solve(N, W, w, v) << endl;
  return 0;
}


Measured memory_bytes: 1920
# 多次元リストの sort に使える
from operator import itemgetter

n = int(input())
x = [0] * n
l = [0] * n
for i in range(n):
    x[i], l[i] = map(int, input().split())

st = sorted([(x[i] - l[i], x[i] + l[i]) for i in range(n)], key = itemgetter(1))

ans = 0
# 最後に選んだ仕事の終了時間
last = - 10 ** 10

for i in range(n):
    if last <= st[i][0]:
        ans += 1
        last = st[i][1]

print(ans)

Measured memory_bytes: 32448
import java.util.Scanner;

//Sum of 4 Integers II
public class Main{

	void run(){
		Scanner sc = new Scanner(System.in);
		int[] a = new int[2001];
		for(int i=0;i<=1000;i++)for(int j=0;j<=1000;j++)a[i+j]++;
		while(sc.hasNext()){
			int s = sc.nextInt(), res = 0;
			for(int i=Math.min(s, 2000);i>=0;i--)res+=s-i<=2000?a[i]*a[s-i]:0;
			System.out.println(res);
		}
	}
	
	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 19620
n = int(input())
a = list(map(int, input().split()))

a.insert(0, 0)
a.append(0)

total = 0
for i in range(0, n+1):
    total += abs(a[i+1]-a[i])

for i in range(1, n+1):
    tmp = abs(a[i]-a[i-1])+abs(a[i+1]-a[i])-abs(a[i+1]-a[i-1])
    print(total - tmp)

Measured memory_bytes: 14048
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <string>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <bitset>
#include <iomanip> 

using ll = long long;
using ull = unsigned long long;
using namespace std;

#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i = 0;(i) < ((int)(n));++(i))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )
#define test(a) cout<<"line:"<<__LINE__<<"["<<(#a)<<": "<<(a)<<"]"<<endl

constexpr int INF = 1e9+7;
constexpr ll INFL = 9*1e18;

constexpr int dx[4] = { 1, 0, -1, 0 };
constexpr int dy[4] = { 0, 1, 0, -1 };

// constexpr int dx[8] = {1, 1, 0,-1,-1,-1, 0, 1};
// constexpr int dy[8] = {0, 1, 1, 1, 0,-1,-1,-1};

int inline digit(ll num){int tmp = 0;while(num){tmp++;num/=10;}return tmp;} // 桁数
template<typename T>inline T SUM(vector<T> vec){return accumulate(all(vec),(T)0);} // vectorの中身を全部足す
template<typename T>inline T digitSum(T num){T sum = 0;while(num){sum+=num%10;num/=10;}return sum;} // 各桁の和
template<typename T>inline T gcd(T a,T b){if(b == 0)return a;return gcd(b,a%b);} // 最大公約数
template<typename T>inline T lcm(T a, T b){T g = gcd(a,b);return a/g*b;} // 最小公倍数
template<typename T>inline T power(T a,T b){T tmp=1;rep(i,b){tmp*=a;}return tmp;} // 累乗
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; }
template<typename T>inline void print(T&& x){cout<<setprecision(32)<<x<<endl;}


// TODO: write
int main() {
  string s;cin>>s;
  int n = s.size();
  if(s[n-1] == 's')s += "es";
  else s+='s';
  print(s);
  return 0;
}

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

typedef pair<int,int> P;
#define ll long long
#define ld long double
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
#define sz(x) ((int)(x).size())
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)

const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;
int main()
{
    int n;
    cin >> n;
    vector<int> c(n-1);
    vector<int> s(n-1);
    vector<int> f(n-1);
    rep(i,n-1)
    {
        cin >> c[i] >> s[i] >> f[i];
    }
    vector<int> ans(n);
    rep(i,n)ans[i] = 0;
    
    for (int i = 0; i <= n-2; i++)
    {
        int temp = 0;
        for (int j = i; j <= n-2; j++)
        {
            if (temp < s[j]) temp = s[j];

            if (temp % f[j] != 0) temp += (f[j] - temp % f[j]);
            temp += c[j];
        }
        ans[i] = temp;
    }
    rep(i,n)
    {
        cout << ans[i] << endl;
    }
    
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mod 1000000007
int main()
{
 string s;
 cin>>s;
 int n=s.length();
 vector<int>a(n+1,0);
 for(int i=0;i<n;i++)
 {
     if(s[i]=='<')
       a[i+1]=a[i]+1;
 }
 for(int i=n-1;i>=0;i--)
 {
     if(s[i]=='>')
        a[i]=max(a[i],a[i+1]+1);
 }
  ll ans=0;
  for(int i=0;i<a.size();i++)
    ans+=a[i];
  cout<<ans;
}


Measured memory_bytes: 2820
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int main(void)
{
    char s[10000];
    int n, i;
    scanf("%d", &n);
    scanf("%s", s);
    for (i = 0; i < strlen(s); i++)
    {
        s[i] = ((s[i] + n) <= 90) ? s[i] + n : s[i] + n - 26;
    }

    printf("%s\n", s);
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,h[114514],dp[114514];
int main() {
	cin>>n;
  for(int i=0;i<n;i++)cin>>h[i];
  dp[1]=abs(h[0]-h[1]);
  for(int i=2;i<n;i++)dp[i]=min(dp[i-2]+abs(h[i-2]-h[i]),dp[i-1]+abs(h[i-1]-h[i]));
  cout<<dp[n-1]<<endl;
	return 0;
}

Measured memory_bytes: 1792
a,b = map(int,input().split())
import math
if a==b:
  print((math.factorial(a)%(10**9+7))**2*2%(10**9+7))
elif abs(a-b)==1:
  print((math.factorial(max(a,b))%(10**9+7))*(math.factorial(min(a,b))%(10**9+7))%(10**9+7))
else:
  print(0)


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

using namespace std;

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

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;

int N;
ll ans = 1;
ll mod = (ll)1e9+7;
int pre = 0;

void solve() {
    cin >> N;
    string S, T;
    cin >> S >> T;
    rep(i,S.size()) {
        if (i+1 < S.size() && S[i] == S[i+1]) {
            if (pre == 0) {
                ans = 6;
            } else if (pre == 1) {
                ans *= 3;
            } else {
                ans *= 2;
            }
            ans %= mod;
            pre = 1;
            i++;
        } else {
            if (pre == 0) {
                ans = 3;
            } else if (pre == 1) {
                
            } else {
                ans *= 2;
            }
            ans %= mod;
            pre = 2;
        }
        //cout << ans << endl;
    }
    cout << ans << endl;
}

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


Measured memory_bytes: 256
#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>
#include <iterator>
#include <numeric>
#include <bitset>
#include <cassert>
#include <functional>

using namespace std;
using Graph = vector<vector<int>>;
typedef long long ll;
typedef pair<ll, ll> P;
inline ll min(ll x, ll y) { return x < y ? x : y; }
inline ll max(ll x, ll y) { return x > y ? x : y; }

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#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 all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << (x) << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)

int main() {
	int A, B, C;
	cin >> A >> B >> C;
	if (A == B) {
		cout << C;
	}
	else if (B == C) {
		cout << A;
	}
	else {
		cout << B;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define INF 100000000000
#define ll long long
#define pll pair<ll, ll>
using namespace std;

int main()
{
  ll N;
  cin >> N;
  vector<ll> odd(100001, 0);
  vector<ll> even(100001, 0);
  for (ll i = 0; i < N; ++i)
  {
    ll v;
    cin >> v;
    if (i % 2 == 0)
    {
      odd.at(v) += 1;
    }
    else
    {
      even.at(v) += 1;
    }
  }
  vector<ll> te = even;
  vector<ll> to = odd;
  sort(te.begin(), te.end());
  sort(to.begin(), to.end());
  ll mo, so, me, se;
  // ll mocnt = 0;
  // ll mecnt = 0;
  for (ll i = 0; i < 100001; ++i)
  {
    if (odd.at(i) == to.at(100000))
    {
      mo = i;
      // mocnt += 1;
    }
    if (even.at(i) == te.at(100000))
    {
      me = i;
      // mecnt += 1;
    }
    if (odd.at(i) == to.at(99999))
    {
      so = i;
    }
    if (even.at(i) == te.at(99999))
    {
      se = i;
    }
  }
  ll ans = odd.at(mo) + even.at(me);
  if (mo == me)
  {
    ans = max(odd.at(so) + even.at(me), odd.at(mo) + even.at(se));
  }
  cout << N - ans << endl;
}


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

template <
    typename TYPE,
    std::size_t SIZE>
std::size_t a_len(const TYPE (&array)[SIZE])
{
    return SIZE;
}

using namespace std;
using ll = long long int;
using vi = vector<ll>;

#define REPS(a, i, n) for (ll(i) = a; (i) < (n); ++(i))
#define REP(i, n) REPS(0, i, n)
#define ALL(x) (x).begin(), (x).end()

const ll INF = 912345678;


int main()
{
    int n;
    vi a;
    cin >> n;
    REP(i,n){
        int c;
        cin >> c;
        a.push_back(c);
    }

    sort(ALL(a));

    if(n%2){
        cout << 0 << endl;
        return 0;
    }

    int l = a[n/2-1];
    int r = a[n/2];


    cout << r-l << endl;
}

Measured memory_bytes: 1400
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

const int MOD = 1e9 + 7;
const int iINF = 1000000000;
const long long int llINF = 1000000000000000000;

using namespace std;
using ll = long long int;
using vv = vector<vector<ll>>;
using edge = struct {
  int to;
  int cost;
};
#define REP(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define AUTO(i, m) for (auto &i : m)
#define ALL(a) (a).begin(), (a).end()
#define MAX(vec) *std::max_element(vec.begin(), vec.end());
#define MIN(vec) *std::min_element(vec.begin(), vec.end());
#define BIT(n, num) std::bitset<(n)>((num)).to_string()
#define REV(T) greater<T>()
#define PQ priority_queue<ll, vector<ll>, greater<ll>>

typedef pair<ll, ll> Pair;
bool pairCompare(const Pair &firstElof, const Pair &secondElof) {
  return firstElof.second > secondElof.second;
}

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

ll LA[200001] = {};
ll RA[200001] = {};

int main() {
  ll N;
  vector<ll> A;
  cin >> N;
  REP(i, 3 * N) {
    ll a = 0;
    cin >> a;
    A.push_back(a);
  }
  ll sum = 0;
  PQ B;
  priority_queue<ll> C;
  REP(i, N) {
    sum += A[i];
    B.push(A[i]);
  }
  LA[N - 1] = sum;
  FOR(i, N, 2 * N) {
    B.push(A[i]);
    sum += A[i];
    sum -= B.top();
    B.pop();
    LA[i] = sum;
  }
  sum = 0;
  FOR(i, 2 * N, 3 * N) {
    sum += A[i];
    C.push(A[i]);
  }
  RA[2 * N] = sum;
  for (ll i = 2 * N - 1; i >= N; i--) {
    C.push(A[i]);
    sum += A[i];
    sum -= C.top();
    C.pop();
    RA[i] = sum;
  }
  ll max = -llINF;
  FOR(i, N - 1, 2 * N) {
    if (LA[i] - RA[i + 1] > max) {
      max = LA[i] - RA[i + 1];
    }
  }
  cout << max << endl;

  return 0;
}


Measured memory_bytes: 8428
#include <iostream>
#include <string>
#include <cctype>
using namespace std;
typedef string::const_iterator State;
int expression(State &begin);
int term(State &begin);
int factor(State &begin);
int number(State &begin);
int expression(State &begin){
	int ret=term(begin);
	while(true){
		if(*begin == '+'){
			begin++;
			ret+=term(begin);
		}else if(*begin == '-'){
			begin++;
			ret-=term(begin);
		}else{
			break;
		}
	}
	return ret;
}
int term(State &begin){
	int ret=factor(begin);
	while(true){
		if(*begin == '*'){
			begin++;
			ret*=factor(begin);
		}else if(*begin == '/'){
			begin++;
			ret/=factor(begin);
		}else{
			break;
		}
	}
	return ret;
}
int number(State &begin){
	int ret=0;
	while(isdigit(*begin)){
		ret*=10;
		ret+= (*begin) -'0';
		begin++;
	}
	return ret;
}
int factor(State &begin){
	if(*begin == '('){
		begin++;
		int ret=expression(begin);
		begin++;
		return ret;
	}else{
		return number(begin);
	}
}
int main(){
	int n;
	cin >> n;
	cin.ignore();
	for(int i=0;i<n;i++){
		string s;
		getline(cin,s);
		State begin=s.begin();
		int ans=expression(begin);
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 1212
#include <iostream>

using namespace std;

int main() {
    int x, y;
    cin >> x >> y;

    for (int i = 0; i <= x; ++i) {
        int legs = i * 2 + (x - i) * 4;
        if (legs == y) {
            cout << "Yes\n";
            return 0;
        }
    }

    cout << "No\n";
}


Measured memory_bytes: 3116
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<functional>
#include<iomanip>
#include<iostream>
#include<numeric>
#include<math.h>
#include<map>
#include<queue>
#include<set>
#include<string>
#include<utility>
#include<vector>
// 追加１
#include <fstream>



using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll mod = 2019;
#define rep(i,n) for(int i=0;i<n;i++)
#define repl(i,s,e) for(int i=s;i<e;i++)
#define reple(i,s,e) for(int i=s;i<=e;i++)
#define revrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()



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

    vector<int> H(N);
    rep(i, N) cin >> H[i];

    //P[i] := 展望台iよりも高い展望台の個数
    vector<int> P(N, 0);

    rep(i, M)
    {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        if(H[a] <= H[b]) P[a]++;
        if(H[b] <= H[a]) P[b]++;
    }

    
    ll count = 0;

    rep(i, N)
    {
        if (P[i] == 0) count++;
    }

    cout << count << endl;

    return 0;
}

Measured memory_bytes: 4000
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <tuple>
#include <numeric>

using namespace std;

typedef long long ll;

int main(void){
    ll n;
    cin >> n;
    cout << 180 + (n - 3) * 180 << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
#define tablesize 1000010
#include <math.h>

int main(void){
    int table[tablesize];
    for(int i=0;i<tablesize;i++){
        table[i]=1;
    }
    int k;
    table[0]=0;
    table[1]=0;
    for(int i=2;i<(int)sqrt(tablesize)+10;i++){
        if(table[i]==1){
            k=2;
            while(k*i<=tablesize){
                table[k*i]=0;
                k++;
            }
        }
    }

    int n;
    int retval;
    while(cin>>n){
        retval=0;
        for(int i=0;i<=n;i++){
            retval+=table[i];
        }
        cout<<retval<<endl;
    }
    return 0;
}



Measured memory_bytes: 6976
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
    vector<int> w(101,101);
    vector<int> w1(101, 101);
   /* vector<int> s1;
    vector<int> s2;*/
    int N=0, sum1=0, sum2=0, ans;

    cin >> N;

    for (int i = 0; i < N; i++) {
        cin >> w[i];
    }

  
    for (int i = 0; i < N; i++) {
        sum1 = 0;
        sum2 = 0;
        for (int j = 0, k = 0; j < N; j++) {
            
            if (k <= i) {
                sum1 += w[k];
                k++;
                if (w[k] == 101)break;
            }
            else {
                sum2 += w[k];
                k++;
                if (w[k] == 101)break;
            }
            
        }
        ans = sum1 - sum2;
        if (ans < 0) {
            ans = -ans;
        }
       
        w1[i] = ans;
    }
   
    sort(w1.begin(), w1.end());

    cout << w1[0];

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using p = pair<int, int>;
#define INF 1001001001
#define PI 3.14159265359
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define repX(i, n , x) for (int i = (int)(x); i < (int)(n); ++i)
#define repB(i, n) for (int i = n; i >= 1; --i)
#define repBX(i, n , x) for (int i = (int)(n); i >= int(X); --i)
#define dup(x,y) (((x)+(y)-1)/(y))

int main() {
    int N,M;
    cin >> N >> M;
    vector<bool> ac(N);
    vector<int> wa(N);
    rep(i,M){
        int p;
        string S;
        cin >> p >> S;
        --p;
        if(S == "WA")if(!ac[p])wa[p]++;
        if(S == "AC")ac[p] = true;
    }
    int acC = 0,waC = 0;
    rep(i,N){
        if(ac[i]){
            acC ++;
            waC += wa[i];
        }
    }
    printf("%d %d\n",acC,waC);
    
    return 0;
}

Measured memory_bytes: 640
const p = (...args) => {
  process.env.NODE_ENV === "test" ? console.log(...args) : ""
}

const solve = (ss) => {
  let maps = []
  // let dif = []
  let all = ss.reduce((acc, n) => acc + n, 0)

  let sum = 0
  let minDif = Infinity
  for (var i = 0; i < ss.length; i++) {
    sum = sum + ss[i]
    maps[i] = [sum, all - sum]
    let dif = Math.abs(sum - (all - sum))
    if (dif < minDif) {
      minDif = dif
    }
  }
  return minDif
  // ...
}

const main = (input) => {
  const [n, ss] = input.split("\n")

  return solve(ss.split(" ").map(Number))
}

if (process.env.NODE_ENV !== "test") {
  const input = require("fs").readFileSync("/dev/stdin", "utf8")
  console.log(main(input.trim()))
}

if (process.env.NODE_ENV === "test") {
  // module.exports = (input) => solve(input.trim())
  // main(``)
  // solve(1, [2, 3, 4])
}


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

#define int long long

using namespace std;
#define REP(i, s, n) for(signed i = (s); i < signed(n); i++)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, n) for(int i = signed(n) - 1; i >= 0; i--)
#define all(co) co.begin(), co.end()
typedef pair<int, int> P;
typedef long long LL;

#ifdef int
const long long INF = 1ll << 62ll;
#else
const singed INF = 1 << 29;
#endif

struct edge{ int from, to, cost; };

int dr[] = { -1, 0, 1, 0 };
int dc[] = { 0, 1, 0, -1 };

template<typename T = int>
vector<vector<T>> vvector(int h, int w, T def = T()){ return move(vector<vector<T>>(h, vector<T>(w, def))); }
class range {
private: struct I{ int x; int operator*(){ return x; }bool operator!=(I& lhs){ return x < lhs.x; }void operator++(){ ++x; } }; I i, n;
public:range(int n) :i({ 0 }), n({ n }){}range(int i, int n) :i({ i }), n({ n }){}I& begin(){ return i; }I& end(){ return n; }
};

signed main()
{
	int h, w;
	while (cin >> h >> w && h)
	{
		auto dp = vvector(h, w + 1);
		int ans = 0;
		rep(i, h)
		{
			stack<P> st;
			st.push(P(0, 0));
			rep(j, w + 1)
			{
				int x = 1;
				if (j < w) cin >> x;

				if (!x) dp[i][j] = 1;
				if (i >= 1 && dp[i - 1][j] && !x)
					dp[i][j] = dp[i - 1][j] + 1;

				int size = dp[i][j];
				if (size == st.top().first) continue;
				else if (size > st.top().first) st.push(P(size, j));
				else
				{
					int beg = j;
					while (!st.empty() && st.top().first > size)
					{
						P p = st.top(); st.pop();
						ans = max(ans, (j - p.second) * p.first);
						beg = p.second;
					}
					if (st.top().first == size) 
						ans = max(ans, (j - st.top().second + 1) * st.top().first);
					else st.push(P(size, beg));
				}
			}
		}

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

Measured memory_bytes: 16572
N = int(input())
mod = 10**9+7


dp = [ [ [ [0] * 4 for _ in range(4)] for _ in range(4)]   for _ in range(N+1)]

for i in range(4):
    for j in range(4):
        for k in range(4):
            if (i == 0 and j == 1 and k == 2) or \
               (i == 0 and j == 2 and k == 1) or \
               (i == 1 and j == 0 and k == 2):
                   continue

            dp[3][i][j][k] += 1

# print(dp[3])
# exit()

restriction = "AGCT" #0: A, 1:G, 2:C, 3:T

for i in range(4, N+1):

    for i2 in range(4):
        for j in range(4):
            for k in range(4): # i2,j,k
                for p in range(4):

                    # AGC, ACG, GAC
                    if   (j == 0 and k ==  1 and p == 2) or \
                         (j == 0 and k ==  2 and p == 1) or \
                         (j == 1 and k ==  0 and p == 2) : #or \
                             continue

                    if   (i2 == 0 and k == 1 and p == 2) or \
                         (i2 == 0 and j == 1 and p == 2) :
                             continue

                    dp[i][j][k][p] = (dp[i][j][k][p] + dp[i-1][i2][j][k]) % mod


ans = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans = (ans + dp[N][i][j][k]) % mod
print(ans)


Measured memory_bytes: 46320
#include<iostream>
#include<vector>

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }
    int cnt = 0;
    for (int i = 1; i < n - 1; i++)
    {
        if (v[i - 1] < v[i] && v[i] < v[i + 1]
        ||  v[i - 1] > v[i] && v[i] > v[i + 1])
        {
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
a,b,k = map(int,input().split())

if b-a < k*2:
    for i in range(a,b+1):
        print(i)
else:
    for i in range(a,b+1)[:k]:
        print(i)
    
    for i in range(a,b+1)[-k:]:
        print(i)
    

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define print(x) cout << (x) << endl;
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    string Snew = "";
    char Li, Lip;
    long long answer = 0;
    bool bbb = false; 
    for (int i = 1; i < S.size(); i++) {
        Lip = S.at(i - 1);
        Li = S.at(i);
        if (Lip == 'A') {
            Snew.append("A");
        }
        else if (Lip == 'B') {
            if (Li == 'C') {
                Snew.append("D");
                i++;
            }
            else {
                Snew.append("B");
            }
        }
        else if (Lip == 'C') {
            Snew.append("C");
        }
    }
    for (int i = 0; i < Snew.size(); i++) {
        if (Snew.at(i) == 'A') {
            int count = 0;
            for (int j = 1; j < Snew.size() - i; j++) {
                if (Snew.at(i + j) == 'D') {
                    answer += (j - count); 
                    count++;
                }
                else if ((Snew.at(i + j) == 'B') || (Snew.at(i + j) == 'C')) {
                    i += (j - 1);
                    break;
                }
                if (i + j + 1 == Snew.size()) {
                    bbb = true;
                }
            }
        }
        if (bbb == true) {
            break;
        }
    }
    print(answer);
}


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

namespace test
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = ReadArrayLong();
            var N = input[0];
            var K = input[1];
            var ope = new List<long>[N];
            for (int i = 0; i < N; i++) ope[i] = new List<long>();
            for (int i = 0; i < N; i++)
            {
                input = ReadArrayLong();
                ope[i].Add(input[0]);
                ope[i].Add(input[1]);
            }
            var sortO = ope.OrderBy(x => x[0]).ToList();

            for (int i = 0; i < N; i++)
            {
                K -= sortO[i][1];
                if (K <= 0) { Console.WriteLine(sortO[i][0]); return; }
            }

            Console.WriteLine();
            Console.ReadLine();
        }

        static string Read() { return Console.ReadLine(); }
        static int ReadInt() { return int.Parse(Read()); }
        static long ReadLong() { return long.Parse(Read()); }
        static int[] ReadArrayInt() { return Read().Split(' ').Select(s => int.Parse(s)).ToArray(); }
        static long[] ReadArrayLong() { return Read().Split(' ').Select(s => long.Parse(s)).ToArray(); }
    }
}

Measured memory_bytes: 32248
#include <cstdio>
#include <algorithm>

#define INF 1000000000

#define MAXN 2009

int alb[MAXN], negru[MAXN], aa[MAXN], nn[MAXN];
int an[MAXN][MAXN], na[MAXN][MAXN], dp[MAXN][MAXN];

int main() {
    int n;
    scanf("%d", &n);

    for (int i = 1; i <= 2 * n; i++) {
        char ch;
        int x;
        scanf(" %c%d", &ch, &x);

        if (ch == 'W')
            alb[x] = i;
        if (ch == 'B')
            negru[x] = i;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = n; j >= 0; j--) {
            aa[i] += j > i && alb[j] < alb[i];
            nn[i] += j > i && negru[j] < negru[i];
            an[i][j] = an[i][j + 1] + (negru[j] < alb[i]);
            na[i][j] = na[i][j + 1] + (alb[j] < negru[i]);
        }
    }

    for (int i = 0; i <= n; i++) {
        for (int j = 1 - bool(i); j <= n; j++) {
            dp[i][j] = INF;
            if (i > 0)
                dp[i][j] = std::min(dp[i][j], dp[i - 1][j] + an[i][j + 1] + aa[i]);
            if (j > 0)
                dp[i][j] = std::min(dp[i][j], dp[i][j - 1] + na[j][i + 1] + nn[j]);
        }
    }

    printf("%d\n", dp[n][n]);

    return 0;
}


Measured memory_bytes: 47488
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace D2019PCA2
{
    class Program
    {
        static void Main(string[] args)
        {
            //スペース区切りで入力されたデータは１番目→input[0]、２番目→input[1] .......の形で受け取られる
            //配列の添え字は０から始める
            //受け取ったデータは文字型なので、整数型に変える
            string[] input = Console.ReadLine().Split(' ');
            int R = int.Parse(input[0]);
            int G = int.Parse(input[1]);
            int B = int.Parse(input[2]);
            int N = int.Parse(input[3]);
            int ans = 0;
            int check = 0;
            for (int r = 0; r <= 3000; r++)
            {
                for (int g = 0; g <= 3000; g++)
                {
                    check = N - (R * r + G * g);
                    if (check>=0&&check%B==0)
                    {
                        ans++;
                    }
                }
            }
            Console.WriteLine(ans);//答えを出力する

        }
    }
}


Measured memory_bytes: 11092