akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<map>
#include<cassert>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
const int mod = 1000000007;
const int inf = 1ll << 61;
typedef pair<int, int> P;
typedef pair<int, P>PP;
int t[100006];
double a[100006];
int l[100006], r[100006];
double perf[400006];
signed main() {
	int n; cin >> n;
	rep(i, n)cin >> t[i] >> a[i];
	int q; cin >> q;
	rep(i, q)cin >> l[i] >> r[i];
	map<int, int>M,M1;
	rep(i, n)M[t[i]]++;
	rep(i, q) {
		M[l[i]]++; M[r[i]]++;
	}
	int now = 0;
	for (auto itr = M.begin(); itr != M.end(); itr++) {
		M1[itr->first] = now; now++;
	}
	rep(i, n)t[i] = M1[t[i]];
	rep(i, q) {
		l[i] = M1[l[i]];
		r[i] = M1[r[i]];
	}
	rep(i, 400000)perf[i] = 1;
	perf[0] = 1e9;
	rep(i, n) {
		perf[t[i] + 1] = (10 - a[i]) / 10;
	}
	rep(i, 399999)perf[i + 1] *= perf[i];
	rep(i, q) {
		printf("%.9lf\n", perf[r[i] + 1] / perf[l[i]]*1e9);
	}
}


Measured memory_bytes: 46968
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::io::{stdin, stdout, Read, Write};
use std::str::FromStr;

#[derive(Default)]
struct Scanner<R: Read> {
    reader: R,
}

impl<R: Read> Scanner<R> {
    fn new(reader: R) -> Scanner<R> {
        Scanner {
            reader,
        }
    }

    fn scan<T: FromStr>(&mut self) -> Option<T> {
        let s = self.reader.by_ref().bytes().map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        s.parse::<T>().ok()
    }

    fn next<T: FromStr>(&mut self) -> T {
        if let Some(s) = self.scan() {
            s
        } else {
            std::process::exit(1);
        }
    }
}

fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin);
    let out = stdout();
    let mut out = out.lock();

    let n: usize = sc.next();
    let mut a = vec![0; n+1];
    for i in 1..(n+1) {
        a[i] = sc.next();
    }
    for i in 1..(n+1) {
        let mut s = format!("node {}: key = {}, ", i, a[i]);
        if i/2 > 0 {
            s += format!("parent key = {}, ", a[i/2]).as_str();
        }
        if i*2 <= n {
            s += format!("left key = {}, ", a[i*2]).as_str();
        }
        if i*2 + 1 <= n {
            s +=  format!("right key = {}, ", a[i*2+1]).as_str();
        }
        writeln!(out, "{}", s).ok();
    }
}


Measured memory_bytes: 5040
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		scan.nextLine();
		while(n-- > 0){
			String s = scan.nextLine();
			if(s.matches("^>'(=+)#\\1~$")) System.out.println("A");
			else if(s.matches("^>\\^(Q=)+~~$")) System.out.println("B");
			else System.out.println("NA");
		}
	}
}

Measured memory_bytes: 13000
#include<bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(i=a;i<b;i++)

void solve(int n,int arr[][3])
{
    int ans[n][3];
    ans[n-1][0]=arr[n-1][0];
    ans[n-1][1]=arr[n-1][1];
    ans[n-1][2]=arr[n-1][2];
    for(int i=n-2;i>=0;i--)
    {
        ans[i][0]=arr[i][0]+max(ans[i+1][1],ans[i+1][2]);
        ans[i][1]=arr[i][1]+max(ans[i+1][0],ans[i+1][2]);
        ans[i][2]=arr[i][2]+max(ans[i+1][0],ans[i+1][1]);
    }
   cout<<max(ans[0][0],max(ans[0][1],ans[0][2]));
}
int main()
{
int n;
cin >> n;
int arr[n][3];
for(int i=0;i<n;i++)
{
    cin>>arr[i][0]>>arr[i][1]>>arr[i][2];
}
solve(n,arr);
}


Measured memory_bytes: 2560
#include <iostream>
#define rep2(x,from,to) for(int x=(from);(x)<(to);(x)++)
#define rep(x,to) rep2(x,0,to)
using namespace std;

int main(){
	int n, y, b, r, t;
	while(cin >> n, n) {
		cin >> y;
		double ret = 1;
		int num = 0;
		rep(i,n) {
			cin >> b >> r >> t;
			double x = 1;
			if(t==1) {
				x = 1.0 + (r*y/100.0);
				if(x>ret) {
					ret = x;
					num = b;
				}
			} else {
				rep(j,y) {
					x *= 1.0 + r/100.0;
				}
				if(x>ret) {
					ret = x;
					num = b;
				}
			}
		}
		cout << num << endl;
	}
}

Measured memory_bytes: 1160
using System;
class Program
{
	static void Main()
	{
	string[] input = Console.ReadLine().Split(' ');//Splitで区切り文字を指定して複数個受け取る。
	int h = int.Parse(input[0]);
	int w = int.Parse(input[1]);
    string result = "";
    string[] masu = new string[h];
	for(int i = 0; i < h; i++)
        {
          masu[i] = Console.ReadLine();	
        }
      
       
        for(int i = 0; i < h; i++)
        {
          result = "";
          for(int j = 0; j < w; j++)
        	{
            int k = 0;
          		for(int a = i-1; a <= i+1; a++)
        		{
                  for(int b = j-1; b <= j+1; b++)
        			{
                    if(a >= 0 && b >= 0 && a < h && b < w)
                    	{
                    	if(masu[a][b] == '#')k++;
                   	    }
                    	
                    }
                  
                }
            if(masu[i][j] == '.')result += k;
            else result += '#';
                  
                
       	    }
          Console.WriteLine(result);
          
        }
	}
  
}


Measured memory_bytes: 11092
#include"bits/stdc++.h"
using namespace std;

//typedef
//------------------------------------------
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<LL, LL> PLL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define PB push_back
#define MP make_pair
#define SORT(c) sort((c).begin(),(c).end())
#define COUT(x) cout<<x<<endl

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double PI = acos(-1.0);
const LL MOD = 1e9 + 7;
const ULL INF= 1e18;
const int dx[]{ 1,-1,0,0 }, dy[]{ 0,0,1,-1 };

//function
//--------------------------------------------
LL gcd(LL, LL);
bool isEven(LL);
void coutY();
void coutN();

int main() {
	LL n; cin >> n;
	VLL b(n); REP(i, n)cin >> b[i];
	VLL ans;
	while (b[0]==1&&!b.empty())
	{
		for (int i = b.size() - 1; i >= 0 && !b.empty();) {
			if (b[i] == i + 1) {
				ans.PB(b[i]);
				b.erase(b.begin() + i);
				i = (int)b.size() - 1;
			}
			else {
				i--;
			}
		}
	}
	if (b.empty()) {
		reverse(ALL(ans));
		REP(i, n)COUT(ans[i]);
	}
	else {
		COUT(-1);
	}
}

LL gcd(LL a, LL b) {
	if (a == 0 || b == 0)return 0;
	if (a < b)swap(a, b);
	if (a % b == 0)return b;
	else gcd(b, a % b);
}
bool isEven(LL a) {
	return !((bool)(a % 2));
}
void coutY() {
	cout << "Yes" << endl;
	return;
}
void coutN() {
	cout << "No" << endl;
	return;
}

Measured memory_bytes: 256
//pragma
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

#define YOU using
#define DONT namespace
#define SAY std

YOU DONT SAY;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<pll> vll;

#define REPP(i,a,b,d) for(int i=a;i<=b;i+=d)
#define REP(i,a,b) REPP(i,a,b,1)
#define REVV(i,a,b,d) for(int i=a;i>=b;i-=d)
#define REV(i,a,b) REVV(i,a,b,1)

#define FOR(i,a) for(int i=0; i<a; i++)
#define FORD(i,a) for(int i=(int)a-1; i>=0; i--)

#define pb push_back
#define F first
#define S second

const int OO = 1e9;
const ll INF = 1e18;

const int irand(int lo,int hi){
	return ((double)rand()/(RAND_MAX + 1.0)) * (hi-lo+1) + lo;
}

const ll lrand(ll lo,ll hi){
	return ((double)rand()/(RAND_MAX + 1.0)) * (hi-lo+1) + lo;
}

#define getc getchar
template<typename T>
T getnum(){
	int sign = 1;
	T ret = 0;
	char c;

	do{
		c = getc();
	}while(c == ' ' || c == '\n');
	if(c == '-')sign = -1;
	else ret = c-'0';
	while(1){
		c = getc();
		if(c < '0' || c > '9')break;
		ret = 10*ret + c-'0';
	}
	return sign * ret;
}

inline void ini(int& x){
	x = getnum<int>();
}

inline void scani(int& x){
	scanf("%d",&x);
}

//end of macro

const ll MOD = 1e9 + 7;

inline ll addmod(ll a, ll b){
    return (a+b)%MOD;
}

const int N = 2e3 + 5;

int n,m;
int a[N], b[N];

int memo[N][N][2];
// stage 0 -> init, choose to take or skip
// stage 1 -> searching on b
int dp(int p, int q, int stage){
    if(p > n)return 1;
    if(q > m){
        if(stage == 0)return 1;
        return 0;
    }
    int& ret = memo[p][q][stage];
    if(ret != -1)return ret;
    
    ret = 0;
    
    if(stage == 0){
        // skip
        ret = addmod(ret, dp(p+1, q, 0));
        
        // take
        ret = addmod(ret, dp(p, q, 1));
    }else{
        ret = addmod(ret, dp(p, q+1, 1)); // stil searching
        
        // take this
        if(a[p] == b[q]){
            ret = addmod(ret, dp(p+1, q+1, 0));
        }
    }
    return ret;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #define endl '\n'
    cout.setf(ios::fixed);
    cout.setf(ios::showpoint);
    cout.precision(10);
    
    cin>>n>>m;
    REP(i,1,n)cin>>a[i];
    REP(i,1,m)cin>>b[i];
    
    memset(memo, -1, sizeof memo);
    cout << dp(1, 1, 0) << endl;
    
    return 0;
}

Measured memory_bytes: 31872
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <cstdlib>
#include <queue>
#include <stack>
#include <time.h>
using namespace std;
int gcd(int a, int b){
	if (b == 0) return a;
	return gcd(b, a % b);
}

int main(){
	int N;
	cin>>N;
	int A[N];
	for(int i=0;i<N;i++){
		cin>>A[i];
	}
	int ans = A[0];
	
	for(int i=1;i<N;i++){
		ans=gcd(ans,A[i]);
	}
	cout<<ans<<endl;
	
	return 0;
}


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

#define EB emplace_back
#define int long long
#define F first
#define S second
#define N 100005
#define ALL(x) x.begin(),x.end()
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)


using namespace std;


int32_t main()
{
    IOS;

    int tt=1;
    //cin>>tt;
    while(tt--)
    {
        int n,k; cin>>n>>k;
        string s; cin>>s;
        int ans = 0;
        if(k == 2 or k == 5)
        {
			for(int i = 0; i < n; i++)
			if((s[i] - '0') % k == 0) ans += (i + 1); 
		}
		else
		{
			map<int,int> mp;
			mp[0] = 1;
			int p = 1;
			int t = 0;
			for(int i = n - 1; i >= 0 ; i--)
			{
				t  = t + (s[i] - '0')*p;
				t %= k;
				t=(t+(s[i]-'0')*p)%k;
				p *= 10;
				p %= k;
				ans += mp[t];
				mp[t]++;
			}			
		}
		cout<<ans<<endl;
    }
    return 0;

}


Measured memory_bytes: 1044
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
	int a [10], i;
	for (i = 0; i < 10; i++) cin >> a[i];
	sort(a, a + 10);
	for (i = 9; i > 6; i--) cout << a[i] << endl;
	return 0;
}

Measured memory_bytes: 3124
import itertools
import numpy as np

N = int(input())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))
nums=np.array(tuple(itertools.permutations(range(1, N+1), N))).tolist()

print(abs(nums.index(P) - abs(nums.index(Q))))

Measured memory_bytes: 34712
#include<stdio.h>
int main(){
	int h,w,x,y,r,i,j;
	scanf("%d %d %d %d %d",&w,&h,&x,&y,&r);
	if(x<=w-r&&x>=r&&y<=h-r&&y>=r){
		printf("Yes\n");
	}
	else{
		printf("No\n");
	}
	return(0);
}

Measured memory_bytes: 584
<?php
function fget_array()   
{   
    return explode(' ', trim(fgets(STDIN)));
}
list($num) = fget_array();   
$places = fget_array(); 
sort($places);
$places = array_values($places);  
$result = $places[0];   
for ($i = 1; $i < $num; $i++) {   
    $result = ($result + $places[$i]) / 2;  
}
echo $result.PHP_EOL;

Measured memory_bytes: 4604
#include<cstdio>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<set>
#include<cstring>
#include<map>
 
 
using namespace std;
#define int long long int
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define mp make_pair
#define pb push_back
#define mod 1000000007

int N,M;
char S[100005];
vector<int> ans;
signed main(){
    scanf("%lld %lld",&N,&M);
    scanf("%s",S);
    //後ろから辿っていく
    int point=N;
    int last_ok_point=N;
    for(int i=N-1;i>=0;i--){
        if(S[i]=='0')last_ok_point=i;
        if(point-i==M||i==0){
            if(point-last_ok_point>0){
                ans.pb(point-last_ok_point);
                point=last_ok_point;
            }
            else{printf("-1\n");return 0;}
        }
    }
    for(int i=ans.size()-1;i>=0;i--){
        printf("%lld",ans[i]);
        if(i!=0)printf(" ");
        else  printf("\n");
    }
    return 0;
}


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

int main() {
    ll a;
    string s;
    ll b = 0;
    cin >> a >> s;
    for(int i = 0; i < s.size(); i++){
        if(s.at(i) == '.'){
            continue;
        }
        char c = s.at(i);
        b = b * 10 + (c - '0');
    }
    cout << a * b / 100 << endl;
}

Measured memory_bytes: 3624
# 20/4/25 Use combinations
import math
N = int(input())
x = [0] * N
y = [0] * N
for i in range(N):
    x[i], y[i] = [int(x) for x in input().split()]

sum_d = 0
for i in range(N):
    for j in range(i + 1, N):
        sum_d += math.sqrt((x[j] - x[i]) ** 2 + (y[j] - y[i]) ** 2)

# (sum_d / NC2) * (N - 1)
print(2 * sum_d / N)

Measured memory_bytes: 3064
def A(x):
  return x + x**2 + x**3


def B(s, t):
  ans = 0
  for i in range(len(s)):
    if s[i] != t[i]:
      ans += 1
  return ans


def C(N):
  pass


def main():
  s = input()
  t = input()
  print(B(s, t))
  # letter = input()
  # A(letter)
  # for x in ['A', 'Z', 'a', 'z']:
  #   A(x)


if __name__ == '__main__':
  main()


Measured memory_bytes: 9568
#include <bits/stdc++.h>
using namespace std;
#define repr(i,k,n) for(int i = (k); i < (n); i++)
#define rep(i,n) repr(i,0,n)
#define ALL(a) begin(a),end(a)
const int INF = 114514810;
const int MOD = 1000000007;
typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int a,b;
	int t[1000];
	cin >> a >> b;
	t[0]=1;
	repr(i,1,999){
		t[i]=i+1+t[i-1];
	}
	rep(i,999){
		int da,db;
		da=a-t[i];
		db=b-t[i+1];
		if (da==db){
			cout << db*-1 << endl;
		}
	}
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  long long n;
  cin >> n;
  if(n%2==1){
    cout << 0;
  }
  else{
    long long i=0;
    long long q=5;
    while(n/2/q!=0){
      i=i+n/2/q;
      q=q*5;
    }
    cout << i;
  }
}

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

int main() {
	long n,m,i,j,k,ans,cur,res;
	cin >> n >> k;
	vector<long> a(n,1);
	for(i=0; i<k; i++){
		cin >> m;
		for(j=0; j<m; j++){
			cin >> cur;
			a[cur-1]=0;
		}
	}
	ans=0;
	for(i=0; i<n; i++){
		if(a[i]==1){
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3628
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		if (n == 1) {
			System.out.println("Hello World");
		}else {
			int a = sc.nextInt();
			int b = sc.nextInt();
			System.out.println(a + b);
		}
	}
}


Measured memory_bytes: 23764
#include<bits/stdc++.h>
#define ALL(c) (c).begin(),(c).end()
#define EACH(i,c) for(auto i=(c).begin();i!=(c).end();++i)
using namespace std;
#define int long long


void solve(long long s){
    set<int> st;
    st.insert(s);
    int i = 1;
    for(;;) {
        if (s % 2 == 0) {
            s = s / 2;
        } else {
            s = 3 * s + 1;
        }
        i++;
        if (st.find(s) != st.end()) {
            cout << i << endl;
            return;
        }
        st.insert(s);
    }
}

signed main(){
    long long s;
    scanf("%lld",&s);
    solve(s);
    return 0;
}


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

int x[10000];
int main(){
	int n;
	int i = 0;
	for (n = 0; n <= 9999; n++) {
		cin >> x[n];
		if (x[n] == 0) break;
		i++;



		cout << "Case " << i << ": " << x[n] << endl;





	}



	return 0;
}



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

int main() {
    int N;
        cin>>N;
    vector<int> a(N);
    int max=0;
    int min=1000;
    for(int i=0;i<N;i++){
        cin>>a.at(i);
        if(max<a.at(i)){
            max=a.at(i);
            //cout<<"max="<<max<<endl;
        }
        if(min>a.at(i)){
            min=a.at(i);
            //cout<<"min="<<min<<endl;
        }
    }
    cout<<max-min<<endl;
return 0;}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
#define FOR(i,a,n) for(ll i=(ll)a;i<(ll)n;i++)
#define RFOR(i,a,n) for(ll i=(ll)n-1;i >= (ll)a;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,0,n)
#define ALL(v) v.begin(), v.end()
#define bra(first,second) '(' << first << ',' << second << ')'
ll MOD = 1000000007;
//ll INF = 21474836470000000;
ll INF = 1001001001001001001;
long double EPS = 1e-11;
long double PI = 3.141592653589793238;
template<typename T>
void remove(std::vector<T>& vector, unsigned int index){
    vector.erase(vector.begin() + index);
}

using Graph = vector<vector<ll>>;

ll A[5][5];
ll B[5][5];

int main(){
    rep(i,3) rep(j,3) cin >> A[i][j];
    ll N;
    cin >> N;
    rep(i,N){
        ll b;
        cin >> b;
        rep(j,3) rep(k,3) if(A[j][k] == b) B[j][k] = 1;
    }
    if((B[0][0] && B[1][1] && B[2][2]) || (B[0][2] && B[1][1] && B[2][0])){
        cout << "Yes" << endl;
    }else{
        rep(i,3){
            if((B[i][0] && B[i][1] && B[i][2]) || (B[0][i] && B[1][i] && B[2][i])){
                cout << "Yes" << endl;
                return 0;
            }
        }
        cout << "No" << endl;
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
#include <iomanip>   //setprecision(10) 

using namespace std;

int main() {
    int A, B, C = 0;

    cin >> A >> B >> C;
    if (A==B&&A!=C) {
        cout <<"Yes";
    } 
    else if (A==C&&A!=B) {
        cout <<"Yes";
    }
    else if (B==C&&B!=A) {
        cout <<"Yes";
        exit(0);
    }
    else cout << "No";

    return 0;
}


Measured memory_bytes: 256
L,R = list(map(int,input().split()))
def main(L,R):
    mod_min = 2019
    if L // mod_min == R // mod_min:
        L %= mod_min
        R %= mod_min
        for i in range(L,R):
            for j in range(i+1, R+1):
                Y = i*j % 2019
                if Y < mod_min:
                    mod_min = Y
    else:
        mod_min = 0
    return mod_min
print(main(L,R))

Measured memory_bytes: 3064
#include <iostream>
#include <cmath>

using namespace std;

const double EPS = 1e-8;

struct Point {
    double x, y;
    Point() {}
    Point(double x, double y) : x(x), y(y) {}
    Point operator+(const Point& p) const { return Point(x + p.x, y + p.y); }
    Point operator-(const Point& p) const { return Point(x - p.x, y - p.y); }
    Point operator*(double k) const { return Point(k * x, k * y); }
    Point operator/(double k) const { return Point(x / k, y / k); }
};
double dot(const Point& a, const Point& b) { return a.x * b.x + a.y * b.y; }
double cross(const Point& a, const Point& b) { return a.x * b.y - a.y * b.x; }
double norm(const Point& a) { return sqrt(dot(a, a)); }
Point rot90(const Point& p) { return Point(p.y, -p.x); } // 時計回りに90度回転 
bool equals(const Point& a, const Point& b) { return abs(a.x - b.x) < EPS && abs(a.y - b.y) < EPS; }
Point unit(const Point& p) { return p / norm(p); }
ostream& operator<<(ostream& os, const Point& p) { return os << "(" << p.x << "," << p.y << ")"; }

int ccw(Point a, Point b, Point c){
    b = b - a; c = c - a;
    if (cross(b, c) > EPS) return +1;      // a,b,cの順に反時計周り
    if (cross(b, c) < -EPS) return -1;     // a,b,cの順に時計周り
    if (dot(b, c) < 0) return +2;          // c--a--b 直線
    if (norm(b) < norm(c)) return -2;      // a--b--c 直線
    return 0;                              // a--c--b 直線
}

struct Line {
    Point a, b;
    Line() {}
    Line(const Point& a, const Point& b) : a(a), b(b) {}
};
bool contains(const Line& l, const Point& p) { return ccw(l.a, l.b, p) % 2 == 0; }
bool parallel(const Line& s, const Line& t) { 
    Point u = s.b - s.a, v = t.b - t.a;
    return abs(abs(dot(u, v)) - norm(u) * norm(v)) < EPS;
}
bool orthogonal(const Line& s, const Line& t) { return abs(dot(s.b - s.a, t.b - t.a)) < EPS; }

istream& operator>>(istream& is, Point& p) { return is >> p.x >> p.y; }
istream& operator>>(istream& is, Line& l) { return is >> l.a >> l.b; }

int main() {
    int Q; cin >> Q;
    for (int i = 0; i < Q; i++) {
        Line s, t;
        cin >> s >> t;
        if (parallel(s, t)) {
            cout << 2 << endl;
        } else if (orthogonal(s, t)) {
            cout << 1 << endl;
        } else {
            cout << 0 << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 1236
#include <cstdio>
#include <cstdlib>
#include <cstring>

struct Node {
	int key;
	Node *next,*prev;
};

Node *nil;

Node *listSearch(int key)
{
	Node *cur=nil->next;
	while (cur!=nil&&cur->key != key)
	{
		cur=cur->next ;
	}
	return cur;
}

void init()
{
	nil=(Node *) malloc (sizeof(Node));
	nil->next=nil;
	nil->prev=nil;
}

void printList()
{
	Node *cur=nil->next ;
	int isf=0;
	while (1)
	{
		if (cur==nil) break;
		if (isf++>0) printf (" ");
		printf ("%d",cur->key );
		cur=cur->next ;
	}
	printf ("\n");
}

void deleteNode (Node *t)
{
	if (t==nil) return ;
	t->prev->next=t->next;
	t->next->prev=t->prev;
	free(t);
}

void deleteFirst ()
{
	deleteNode (nil->next);
}

void deleteLast()
{
	deleteNode (nil->prev);
}

void deleteKey(int key)
{
	deleteNode (listSearch(key));
}

void insert(int key)
{
	Node *x=(Node *) malloc (sizeof(Node));
	x->key=key;
	x->next =nil->next;
	nil->next->prev=x;
	nil->next=x;
	x->prev=nil;
}

int main ()
{
	int key,n,i;
	int size=0;
	char com[20];
	int np=0,nd=0;
	scanf ("%d",&n);
	init();
	for (i=0;i<n;i++)
	{
		scanf("%s%d",com,&key);
		if (com[0]=='i')
		{
			insert(key);np++;size++;
		}
		else if (com[0]=='d')
		{
			if (strlen(com)>6)
			{
				if (com[6]=='F') deleteFirst();
				else if (com[6]=='L') deleteLast();
			}
			else {
				deleteKey(key);nd++;
			}
			size--;
		}
	}
	printList();
}


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

using namespace std;

int main() {
    
    int i;
    string s;
    cin>>s;
    for(i=0;i<s.length();i++)
    {
        if(s[i]=='?')
        printf("%c", 'D');
        else
        printf("%c", s[i]);
    }
    
    
    
    
    
    
    return 0;
}

Measured memory_bytes: 3752
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
using namespace std;
int N, M;
int main() {
	cin >> N >> M;
	int tmp = 0;
	for (int i = 1; true; i++) {
		tmp += i;
		if (i==M-N) {
			cout << tmp - M << endl;
			break;
		}
	}
	return 0;
}

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

int main(){
	//freopen("in.txt","r",stdin);
	int h[25];
	int n,cnt = 0;
	bool f = true;
	scanf("%d",&n);
	for(int i = 0;i <n ;i ++) scanf("%d",&h[i]);
	for(int i = 0;i < n;i ++){
		f = true;
		for(int j = 0;j < i; j ++){
			if(h[i]<h[j]) f = false;
		} 
		if(f) cnt ++;
	}
	printf("%d",cnt);	
	//fclose(stdin);
    return 0;
}


Measured memory_bytes: 256
import java.util.*;
import java.io.*;
import java.awt.geom.*;
import java.math.*;

public class Main {

	static final Scanner in = new Scanner(System.in);
	static final PrintWriter out = new PrintWriter(System.out,false);
	static boolean debug = false;

	public static int[][][] directedGraph(int n, int[] s, int[] t, int[] cost) {
		int[] cnt = new int[n];
		for (int i : s) cnt[i]++;

		int[][][] g = new int[n][][];
		for (int i=0; i<n; i++) g[i] = new int[cnt[i]][2];
		for (int i=0; i<s.length; i++) {
			int from = s[i];
			int to = t[i];

			g[from][--cnt[from]][0] = to;
			g[from][cnt[from]][1] = cost[i];
		}

		return g;
	}

	public static long[] dijkstra(int[][][] g, int source) {
		int n = g.length;

		final long[] d = new long[n];
		Arrays.fill(d, Integer.MAX_VALUE/2);
		d[source] = 0;

		TreeSet<Integer> pQ = new TreeSet<Integer>(new Comparator<Integer>(){
			public int compare(Integer a, Integer b) {
				if (d[a] != d[b]) return d[a] > d[b] ? 1 : -1;
				return a > b ? 1 : -1;
			}
		});
		pQ.add(source);

		while (!pQ.isEmpty()) {
			int cur = pQ.pollFirst();

			for (int i=0; i<g[cur].length; i++) {
				int next = g[cur][i][0];
				long dist = d[cur] + g[cur][i][1];
				if (dist < d[next]) {
					pQ.remove(next);
					d[next] = dist;
					pQ.add(next);
				}
			}
		}

		return d;
	}

	static boolean solve() {
		int n = in.nextInt();
		int m = in.nextInt();
		int s = in.nextInt() - 1;
		int g1 = in.nextInt() - 1;
		int g2 = in.nextInt() - 1;
		if (n + m == 0) return false;

		int[] v1 = new int[m];
		int[] v2 = new int[m];
		int[] c = new int[m];
		for (int i=0; i<m; i++) {
			v1[i] = in.nextInt() - 1;
			v2[i] = in.nextInt() - 1;
			c[i] = in.nextInt();
		}

		int[][][] g = directedGraph(n, v1, v2, c);
		long[] ds = dijkstra(g, s);

		long ans = ds[g1] + ds[g2];

		for (int i=0; i<n; i++) {
			if (i == s) continue;
			long[] d = dijkstra(g, i);
			ans = Math.min(ans, ds[i] + d[g1] + d[g2]);
		}

		out.println(ans);

		return true;
	}



	public static void main(String[] args) {
		debug = args.length > 0;
		long start = System.currentTimeMillis();

		while(solve());
		out.flush();

		long end = System.currentTimeMillis();
		dump((end-start) + "ms");
		in.close();
		out.close();
	}

	static void dump(Object... o) { if (debug) System.err.println(Arrays.deepToString(o)); }
}

Measured memory_bytes: 69516
#include <stdio.h>
#include <cstdlib>		// abs()

namespace
{
const int MAX = 100000000;		// 座標の最大・最小の位置
int N;	// 学生の総数
int M;	// チェックポイントの総数
int NX[ 51 ];	// 学生の X 座標
int NY[ 51 ];	// 学生の Y 座標
int MX[ 51 ];	// チェックポイントの X 座標
int MY[ 51 ];	// チェックポイントの Y 座標
int A[ 51 ];	// 学生の移動先のチェックポイントの番号
}

int main( int argc, char *argv[] )
{
int i;
int j;
int iNum;		// 学生の移動先のチェックポイントの番号
int iLen;		// マンハッタン距離
int iChk;

	// N M を取得
	scanf( "%d", &N );
	if( N < 1 || N > 50 ) return 0;

	scanf( "%d", &M );
	if( M < 1 || M > 50 ) return 0;

	// 学生の座標を取得
	for( i = 1; i <= N; i++ )
	{
		scanf( "%d", &NX[ i ] );
		if( NX[ i ] < - MAX || NX[ i ] > MAX ) return 0;
		scanf( "%d", &NY[ i ] );
		if( NY[ i ] < - MAX || NY[ i ] > MAX ) return 0;
	}

	// チェックポイントの座標
	for( j = 1; j <= M; j++ )
	{
		scanf( "%d", &MX[ j ] );
		if( MX[ j ] < - MAX || MX[ j ] > MAX ) return 0;
		scanf( "%d", &MY[ j ] );
		if( MY[ j ] < - MAX || MY[ j ] > MAX ) return 0;
	}

	// 各学生の移動先のチェックポイントの番号を算出
	for( i = 1; i <= N; i++ )
	{
		iNum = 0;
		iLen = - 1;
		for( j = 1; j <= M; j++ )
		{
			iChk = abs( NX[ i ] - MX[ j ] ) + abs( NY[ i ] - MY[ j ] );
			if( iLen < 0 || iLen > iChk )
			{
				iNum = j;
				iLen = iChk;
			}
		}

		A[ i ] = iNum;
	}

	// 出力
	for( i = 1; i <= N; i++ ) printf( "%d\n", A[ i ] );

	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define FasterIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define mk make_pair
#define ff first
#define ss second
typedef long long ll;
typedef double db;
const int MX=100000;
vector<int>g[MX];
int node[MX+5];
int dfs(int x)
{
    if(~node[x])return node[x];
    node[x]=0;
    for(int i=0;i<g[x].size();i++)
    {
        int ad=g[x][i];
        node[x]=max(node[x],1+dfs(ad));
    }
    return node[x];
}
int main()
{
    FasterIO;
    int i,j,k,n,m,x,y;
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>x>>y;
        g[x].pb(y);
    }
    int mx=0;
    mem(node,-1);
    for(i=1;i<=n;i++)
    {
        mx=max(mx,dfs(i));
    }
    cout<<mx<<endl;
    return 0;
}


Measured memory_bytes: 8192
#include <stdio.h>

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




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

using namespace std;

int a[200001];
int used[200001];
int d[200001];

int main () {	
	int n;
	cin >> n;
	int mx = 0;
	for (int i = 1;i <= n;i ++) {
		cin >> a[i];
		d[i] = d[used[a[i] - 1]] + 1;
		used[a[i]] = i;
		mx = max (mx, d[i]);
	}
	cout << n - mx;
	return 0;
}

Measured memory_bytes: 2560
def main():
    s = list(input())
    s = s[::-1]

    l = [[[] for j in range(3)] for i in range(673)]
    l[0][0].append(0)
    mo = 0
    ten = 1
    mod = 673
    now = 0
    ans = 0
    for i in range(len(s)):
        a = int(s[i])*ten
        mo = (mo+a)%3
        now = (now+a)%mod
        if l[now][mo]:
            ans += len(l[now][mo])
        l[now][mo].append(i+1)
        ten *= 10
        ten %= 2019
    print(ans)
    
if __name__ == "__main__":
    main()

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

int day(int x, int y) {
    return (x + y - 1) / y;
}

int L, A, B, C, D;
int main() {
    cin >> L >> A >> B >> C >> D;
    cout << L - max(day(A, C), day(B, D)) << endl;
    return 0;
}

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

using namespace std;
using ll =long long;
#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cerr << #x << " = " << (x) << endl;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
void coY() {cout <<"Yes"<<endl;}
void coN(){cout <<"No"<<endl;}
const int mod = 1e9+7;
//Write From this Line
typedef pair<int,int> P;
const int INF = 10101000;
const int di[] = {-1,0,1,0};
const int dj[]= {0,1,0,-1};
int main()
{
	int h , w ;
	cin >> h >> w ;
	int ans = 0 ;
	vector<string> s(h);
	rep(i,h) cin >>s[i];
	rep(si,h)rep(sj,w){//スタート位置全探索
		if(s[si][sj] == '#') continue;
		vector<vector<int>> dist(h,vector<int>(w,INF));
		queue<P> q;
		auto update = [&](int i, int j, int x){
			//マスi,jの値をxでupdateしようとして、出来るならqueueにつっこむ
			if(dist[i][j] != INF) return;
			/*まだ来てないなら*/
			dist[i][j] = x; 
			q.push(P(i,j)); //.emplace(i,j);
		};
		update(si,sj,0);
		while (!q.empty()) {
			int i = q.front().first;
			int j = q.front().second;
			q.pop();
			rep(dir,4){
				int ni = i+di[dir], nj = j+dj[dir]; 
				if(ni<0 || ni>=h || nj<0 ||nj>=w)continue;
				if(s[ni][nj] == '#') continue;
				update(ni,nj,dist[i][j]+1);
			}
		}
		rep(i,h)rep(j,w){
			if(dist[i][j] == INF)continue;
			ans = max(ans,dist[i][j]);
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = br.readLine();
		String[] cut = line.split("");

		int x = Integer.parseInt(cut[0]);
		int y = Integer.parseInt(cut[1]);
		System.out.println(y == 9 || x == 9 ? "Yes" : "No");

	}

}

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

int main(){
  int x,n;
  cin >> x >> n;
  if(n==0){
    cout << x << endl;
    return 0;
  }
  int p[n];
  int count[101] = {0};
  int flag = 0;
  rep(i,0,n){
    cin >> p[i];
    if(p[i]==x) flag = 1;
    count[p[i]]++;
  }

  if(flag == 0) cout << x << endl;
  else{
    int i = 1;
    while(1){
      int a = x+i,b = x-i;
      if(count[b]==0){
        cout << b << endl;
        break;
      }
      else if(count[a]==0){
        cout << a << endl;
        break;
      }
      else i++;
    }
  }

  return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define ULL(...) ull __VA_ARGS__;in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;in(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;in(__VA_ARGS__)
#define vec(type,name,...) vector<type> name(__VA_ARGS__)
#define VEC(type,name,size) vector<type> name(size);in(name)
#define vv(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__))
#define VV(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__));in(name)
#define vvv(type,name,h,w,...) vector<vector<vector<type>>>name(h,vector<vector<type>>(w,vector<type>(__VA_ARGS__)))
inline int scan(){ return getchar(); }
inline void scan(int &a){ scanf("%d", &a); }
inline void scan(unsigned &a){ scanf("%u", &a); }
inline void scan(long &a){ scanf("%ld", &a); }
inline void scan(long long &a){ scanf("%lld", &a); }
inline void scan(unsigned long long &a){ scanf("%llu", &a); }
inline void scan(char &a){ cin >> a; }
inline void scan(float &a){ scanf("%f", &a); }
inline void scan(double &a){ scanf("%lf", &a); }
inline void scan(long double &a){ scanf("%Lf", &a); }
inline void scan(vector<bool> &vec){ for(unsigned i = 0; i < vec.size(); i++) { int a; scan(a); vec[i] = a; } }
inline void scan(string &a){ cin >> a; }
template<class T> inline void scan(vector<T> &vec);
template<class T, size_t size> inline void scan(array<T, size> &vec);
template<class T, class L> inline void scan(pair<T, L> &p);
template<class T, size_t size> inline void scan(T (&vec)[size]);
template<class T> inline void scan(vector<T> &vec){ for(auto &i : vec) scan(i); }
template<class T, size_t size> inline void scan(array<T, size> &vec){ for(auto &i : vec) scan(i); }
template<class T, class L> inline void scan(pair<T, L> &p){ scan(p.first); scan(p.second); }
template<class T, size_t size> inline void scan(T (&vec)[size]){ for(auto &i : vec) scan(i); }
template<class T> inline void scan(T &a){ cin>>a; }
inline void in(){}
template <class Head, class... Tail> inline void in(Head &head, Tail&... tail){ scan(head); in(tail...); }
inline constexpr ll gcd(ll a,ll b){if(!a||!b)return 0;while(b){ll c=b;b=a%b;a=c;}return a;}
inline constexpr ll lcm(ll a,ll b){if(!a||!b)return 0;return a*b/gcd(a,b);}
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; }
using Graph = vector<vector<int>>;
/* 4方向への隣接頂点への移動を表すベクトル */
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

const long long INF = 1LL << 60;
int main(){
    INT(TD);
    INT(TA);
    INT(ED);
    INT(EA);

    int tc = (ED+TA-1)/TA;
    int ec = (TD+EA-1)/EA;

    if(tc < ec + 1){
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }


   
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main()
{
  int n,m,c;
  cin >> n >> m >> c;
  
  int b[m];
  int a[n][m];
  rep(i,m) cin >> b[i];
  rep(i,n){
    rep(j,m){
      cin >> a[i][j];
    }
  }
  
  int ans = 0;
  rep(i,n){
    int sum = 0;
    rep(j,m){
      sum += a[i][j] * b[j];
    }
    sum += c;
    if(sum > 0){
      ans++;
    }//if
  }//rep
  
  cout << ans << endl;
}

Measured memory_bytes: 3596
#include <stdio.h>
using namespace std;

int n, q;
char s[200001], t[200001], d[200001];

char last_place(int index){
    for(int i=0; i<q; i++){
        if(s[index]==t[i]){
            if(d[i]=='R') index++;
            else index--;
        }
        if(index==-1) return 'l'; // lift
        else if(index==n) return 'r'; // right
    }
    return 'i'; // inside
}

int l_limit(int l, int r){
    int mid = (r + l) / 2;
    if(mid == r) return mid-1;
    else if(mid == l) return mid;

    char result = last_place(mid);
    if(result == 'l') return l_limit(mid, r);
    return l_limit(l, mid);
}

int r_limit(int l, int r){
    int mid = (r + l) / 2;
    if(mid == r) return mid;
    else if(mid == l) return mid + 1;

    char result = last_place(mid);
    if(result == 'r') return r_limit(l, mid);
    return r_limit(mid, r);
}

int main(){
    scanf("%d%d", &n, &q);
    scanf("%s", s);
    for(int i=0; i<q; i++){
        scanf(" %c %c", &t[i], &d[i]);
    }

    int vanish_left = l_limit(-1, n) + 1;
    int vanish_right = n - r_limit(-1, n);

    printf("%d\n", n - vanish_left - vanish_right);
    return 0;
}


Measured memory_bytes: 768
#include <stdio.h>
#include <string.h>

int main()
{
	char str[21];
	int i, len;

  scanf("%s", str);

	len = strlen(str);

  for (i = 0; i < len/2; i++) {
    char temp = str[i];
    str[i] = str[len - 1 - i];
    str[len - 1 - i] = temp;
  }

  printf("%s\n", str);

  return 0;
}

Measured memory_bytes: 520
n,m = map(int,input().split())
count = 0
lmax = 0
rmin = 100000
for i in range(m):
  l,r = map(int,input().split())
  lmax = max(l,lmax)
  rmin = min(r,rmin)
print(max(rmin-lmax+1,0))

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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ALL(a)     (a).begin(),(a).end()
#define RALL(a)     (a).rbegin(),(a).rend()
#define PRINT(a)   cout << (a) << endl

#define pb push_back
#define eb emplace_back
#define Fi first
#define Se second

#define debug(x) cerr << x << " " << "(L:" << __LINE__ << ")" << '\n';

using ll = long long int;
using P = pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using pii = pair<int, int>;

template <typename T> using PQ = priority_queue<T>;
template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;

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

const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1e9 + 7;

ll dp[3001][3001][4];

int main(){
  int r,c,k;
  cin >> r >> c >> k;
  
  map<P, int> mp;

  REP(i,k){
    int rr,cc,v;
    cin >> rr >> cc >> v;
    mp[make_pair(rr,cc)]=v;
  }

  FOR(i,1,r+1)FOR(j,1,c+1){
    if(mp.end() != mp.find(make_pair(i,j))){
      ll v = mp[make_pair(i,j)];
      FOR(k,1,4){
        dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k-1]+v);        
      }
      FOR(k,1,4){
        REP(l,4){
          dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][l]+v);        
        }
      }
      REP(k,4){
        dp[i][j][k] = max(dp[i][j][k], max(dp[i-1][j][k], dp[i][j-1][k]));        
      }
    }else{
      REP(k,4){
        dp[i][j][k] = max(dp[i][j][k], max(dp[i-1][j][k], dp[i][j-1][k]));        
      }
    }
  }

  ll ans = 0;
  REP(i,4)chmax(ans, dp[r][c][i]);

  // REP(i,r+1)REP(j,c+1)REP(k,4){
  //   cout << dp[i][j][k] << endl;
  // }

  cout << ans << endl;

}



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

using namespace std;

int main(int argc, char const *argv[]) {
  string t, p;  cin >> t >> p;
  int len = p.size();
  if (t.size() >= len) {
    for (int i = 0; i < t.size() - len + 1; ++i) {
      string s;
      s = t.substr(i, len);
      if (s == p) cout << i << '\n';
    }
  }

  return 0;
}



Measured memory_bytes: 3904
#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
#include <algorithm>
#include <map>

using namespace std;
using ll = long long;
const ll INF = 1e9;

int main() {
    int N;
    ll A, B, ans = 0;
    cin >> N >> A >> B;
    ll X[N];
    for (int i = 0; i < N; i++) cin >> X[i];

    for (int i = 0; i < N-1; i++) {
        ans += min(B, A * (X[i+1] - X[i]));
    }

    cout << ans << endl;

    return 0;
}

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

using namespace std;

//typedef pair<int, int> P;
#define int long long
#define ll long long
#define mod 1000000007
#define INF (1LL<<60)

int func(int h, int w){
	int a[3];
	int m = INF;
	for (int i = 1; i < h; i++){
		// 縦横パターン
		a[0] = i*w;
		a[1] = (h - i)*(w / 2);
		a[2] = h*w - a[0] - a[1];
		m = min(m, *max_element(a, a + 3) - *min_element(a, a + 3));
	}
	// 3等分パターン
	if (h % 3==0) m=0;
	else m = min(m, w);

	return m;

}

signed main(){

	int H, W;
	cin >> H >> W;

	int ans = min(func(H, W), func(W, H));
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <iomanip>
#include <cmath>
#include <stack>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <math.h>
#include <complex>
using ll = long long;
using namespace std;
int const MOD = 1e9 + 7;
ll const INF = (1LL << 50);
#define rep(i, n) for (int i = 0; i < (n); i++)

using P = pair<ll, ll>;
bool operator<(const P &a, P &b)
{
    if (a.first == b.first)
        return a.second < b.second;
    return a.first < b.first;
}

struct Node
{
    ll from, to, cost;
};
Node es[2010];
ll d[2010];
int N, M;

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

    for (int i = 0; i < M; ++i)
    {
        ll a, b, c;
        cin >> a >> b >> c;
        a--;
        b--;
        c = -c;
        es[i] = {a, b, c};
    }

    for (int i = 0; i < N; ++i)
        d[i] = INF;

    d[0] = 0;
    for (int i = 0; i < N - 1; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            Node e = es[j];
            if (d[e.from] != INF && d[e.to] > d[e.from] + e.cost)
            {
                d[e.to] = d[e.from] + e.cost;
            }
        }
    }
    bool negative[1010];
    ll ans = -d[N - 1];
    for (int i = 0; i < N; ++i)
    {
        negative[i] = false;
    }

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            Node e = es[j];
            if (d[e.from] != INF && d[e.to] > d[e.from] + e.cost)
            {
                d[e.to] = d[e.from] + e.cost;
                negative[e.to] = true;
            }

            if (negative[e.from])
                negative[e.to] = true;
        }
    }

    if (negative[N - 1])
        cout << "inf" << endl;
    else
    {
        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define repe(i, n) for(int (i) = 0; i <= (n); (i)++)
#define repr(i, n) for(int (i) = (n); (i) > 0; --(i))
#define repre(i, n) for(int (i) = (n); (i) >= 0; --(i))
#define elm1(pair) (pair).first
#define elm2(pair) (pair)).second
typedef long long ll;
typedef unsigned long long ull;
const ull MOD = 1000000007;
ull mpow(ull a, ull n);
ull inv_mod(ull a){return mpow(a, MOD-2);}

ull mpow(ull a, ull n)
{
    ull ans = 1;
    while(n>>=1){
        if(n & 1)(ans *= a)%= MOD;
        (a*=a)%=MOD;
    }
    return ans;
}

ull nCr(ull n, ull r)
{
    vector<ull> factorial(n+1);
    factorial[0]=1;
    rep(i, n)factorial[i+1] = factorial[i]*(i+1)%MOD;
    return factorial[n]*(inv_mod(factorial[n-r])%MOD*inv_mod(factorial[r])%MOD) % MOD;
}

ll dp[3000][3000] = {0};

//max manpuku
ll naps(vector<pair<ll, ll>> F, ll T, ll n, ll M)
{
    if(n >= F.size())return M;
    if(T <= 0.5)return M;
    return max(naps(F, T-F[n].first, n+1, M+F[n].second), naps(F, T, n+1, M));
}

int main()
{
    int N;
    cin >> N;
    vector<int> h(N);
    rep(i, N)cin >> h[i];
    vector<int> dp(N);
    dp[0] = 0;dp[1] = abs(h[0] - h[1]);
    for(int i = 2; i < N; i++){
        dp[i] = min(dp[i-2]+abs(h[i] - h[i-2]), dp[i-1]+abs(h[i] - h[i-1]));
    }
    cout << dp[N-1] << endl;

    return 0;
}


Measured memory_bytes: 1024
package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"math"
	"os"
	"sort"
	"strconv"
)

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func lowerBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	return idx
}

func upperBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	return idx
}

type pair struct {
	first, second int
}

type pairs []pair

func (p pairs) Len() int {
	return len(p)
}

func (p pairs) Swap(i, j int) {
	p[i], p[j] = p[j], p[i]
}

func (p pairs) Less(i, j int) bool {
	if p[i].first == p[j].first {
		return p[i].second > p[j].second
	}
	return p[i].first > p[j].first
}

// Priority Queue
// Item :
type Item struct {
	priority, index int
}

// PQ :
type PQ []*Item

func (pq PQ) Len() int {
	return len(pq)
}

func (pq PQ) Less(i, j int) bool {
	return pq[i].priority > pq[j].priority
}

func (pq PQ) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}

// Push :
func (pq *PQ) Push(x interface{}) {
	n := len(*pq)
	item := x.(*Item)
	item.index = n
	*pq = append(*pq, item)
}

// Pop :
func (pq *PQ) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	item.index = -1
	*pq = old[0 : n-1]
	return item
}

// End Priority Queue

const inf = math.MaxInt64 / 16
const mod = 998244353

func main() {
	sc.Split(bufio.ScanWords)
	N := getInt()
	tails := make(pairs, N+1)
	index := make([]int, N+1)
	for i := 0; i < N; i++ {
		x, d := getInt(), getInt()
		tails[i] = pair{x + d, x}
		index[i] = x
	}
	tails[N] = pair{inf, inf + 1}
	index[N] = inf
	N++
	sort.Sort(tails)
	sort.Ints(index)
	// out(tails, index)

	pq := make(PQ, 0)
	heap.Init(&pq)
	dict := make(map[int]int)

	r := 0
	l := make([]int, N)
	for i := 0; i < N; i++ {
		dict[index[i]] = i
		l[i] = -1
	}

	for i := N - 1; i >= 0; i-- {
		for r < N && tails[r].first > index[i] {
			heap.Push(&pq, &Item{tails[r].second, 0})
			r++
		}
		for pq.Len() > 0 {
			item := heap.Pop(&pq).(*Item)
			if item.priority < index[i] {
				l[i] = dict[item.priority]
				heap.Push(&pq, item)
				break
			}
		}
	}

	dp := make([]int, N)
	dpSum := make([]int, N)
	dp[0] = 1
	dpSum[0] = 1
	for i := 1; i < N; i++ {
		dp[i] = dpSum[i-1]
		if l[i]-1 >= 0 {
			dp[i] -= dpSum[l[i]-1]
		}
		if l[i] == -1 {
			dp[i]++
		}
		dp[i] %= mod
		dpSum[i] = (dpSum[i-1] + dp[i]) % mod
	}

	if dp[N-1] < 0 {
		dp[N-1] += mod
	}

	out(dp[N-1])
}


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

int main(){
  int num[32]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  int k;
  cin >> k;

  
  
  cout << num[k-1] << endl;
  return 0;
}


Measured memory_bytes: 256