akhauriyash/Code-Regression huggingface dataset:
from sys import stdin
from itertools import combinations_with_replacement,product

n,m = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(m)]
p = list(map(int,stdin.readline().rstrip().split()))

hai = [0,1]
hai = list(product(hai, repeat=n))

point = 0

for i in range(len(hai)):
    h = list(hai[i])
    kai = 0
    for j in range(m):
        gou = 0
        for k in range(1,len(li[j])):
            if h[li[j][k]-1] == 1:
                gou += 1
        if p[j] != gou%2:
            kai += 1
    if kai == 0:
        point += 1
print(point)

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

int main(void){
  int n; cin >> n;
  int p[n];
  for(int i=0; i<n; i++){
    cin >> p[i];
  }
  
  int count = 0;
  vector<int> sorted(3);
  for(int i=1; i<n-1; i++){
    sorted = {p[i-1], p[i], p[i+1]};
    sort(sorted.begin(), sorted.end());
    if(sorted[1] == p[i]) count++;
  }
  
  cout << count << endl;
  
  return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
from collections import *

def dfs(n, x):
    if n==0:
        return 1
        
    s = 2**(n+1)-3
    
    if x<=1:
        return 0
    elif x<=1+s:
        return dfs(n-1, x-1)
    elif x==2+s:
        return dfs(n-1, s)+1
    elif x<=2+2*s:
        return dfs(n-1, s)+1+dfs(n-1, x-2-s)
    else:
        return 2*dfs(n-1, s)+1

N, X = map(int, input().split())
print(dfs(N, X))

Measured memory_bytes: 38384
import sys
def input():return sys.stdin.readline()[:-1]
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())

D=N()
c=[0]+L()
s=[[0]*27]+[[0]+L() for i in range(D)]

dp=[]
T=[0]
ld=[0]*(27)
for i in range(1,D+1):
    ma=0
    t=0
    for j in range(1,27):
        tmp=s[i][j]+(i-ld[j])*(D-i+1)*c[j]
        if tmp>ma:
            ma=tmp
            t=j
    T.append(t)
    ld[t]=i
        
sc=sum(c)
def point():
    ld=[0]*(27)
    score=-sc*((D+1)*D//2)
    for i in range(1,D+1):
        t=T[i]
        score+=s[i][t]+(i-ld[t])*(D-i+1)*c[t]
        ld[t]=i
    return score

now=point()
import random
for i in range(400000):
    d1,q1=random.randrange(1,D+1),random.randrange(1,27)
    d2,q2=random.randrange(1,D+1),random.randrange(1,27)
    old1=T[d1]
    old2=T[d2]
    T[d1]=q1
    T[d2]=q2
    new=point()
    if new>now:
        now=new
    else:
        T[d1]=old1
        T[d2]=old2

for i in T[1:]:
    print(i)

Measured memory_bytes: 83144
#include <bits/stdc++.h>
using namespace std;
typedef long long lo;
typedef vector<lo> vl;
typedef vector<vl>vll;
#define all(v) (v).begin(), (v).end()
#define debug(x) cerr<<#x<<" = "<<x<<endl;
#define REPV(a, b, c) for (lo(a) = b; (a) < (c); (a)++) 
#define REP(a,b) for(lo i =(a) ;i<(b);i++)

template <typename T>

istream &operator>>(istream &in, vector<T> &v)
{
	for (unsigned i = 0; i < v.size(); i++)
		in >> v[i];
	return in;
}


void solve(){

	lo N; cin>>N; vl A(N); cin>>A; lo current_save = 1000;
	for(int i=1;i<N;i++){
		lo x = 0;
		if(A[i]>A[i-1]){
			x = A[i]*(current_save/A[i-1]);
			current_save = current_save%A[i-1];
			}
			
			current_save+=x;
		
		

	}
	cout<<current_save<<endl;

}


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

Measured memory_bytes: 3652
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#define MOD ((int)1e9 + 7)
using namespace std;
   
void down(string &str){
  for(int i=0;i<str.size();++i){
    str[i] -='a';
  }
}

int main(){
  int N;
  cin >> N;
  string a,b;
  cin>>a>>b;
  down(a);
  down(b);
  vector<int> line(26,0);
  line[a[0]] = 1;
  for(int i=1;i<N-1;++i){
    line[a[i]] = (line[a[i]] + line[b[i]]) % MOD;
  }
  cout << line[b[b.size()-1]] << endl;
  return 0;
}


Measured memory_bytes: 3276
n,m,x,y=map(int,input().split())
tmpx=x
tmpy=y
li_x=list(map(int,input().split()))
li_y=list(map(int,input().split()))
for i in range(n):
  tmpx=max(tmpx,li_x[i])
for j in range(m):
  tmpy=min(tmpy,li_y[j])
if tmpx+1<=tmpy:
  print('No War')
else:
  print('War')

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef set<int> si;
typedef map<string, int> msi;
typedef greater<int> gt;
typedef priority_queue<int, vector<int>, gt> minq;
typedef long long ll;
const ll INF = 1e18L + 1;
//clang++ -std=c++11 -stdlib=libc++ 

int main() {
  int H,W; cin>>H>>W;
  vector<string> maze(H);
  rep(i,H) {
    cin >> maze[i];
  }
  rep(i,H) rep(j,W) {
    if (maze[i][j] == '#') continue;
    int cnt = 0;
    int dx[]={0, 1, 1, 1, 0, -1, -1, -1}, dy[]={1,1,0,-1,-1,-1,0,1};
    for (int k=0; k<8; k++) {
      int x = j+dx[k], y = i+dy[k];
      if (x>=0 && x<W && y>=0 && y<H && maze[y][x] == '#') cnt++;
    }
    maze[i][j] = '0'+cnt;
    // maze[i][j] = static_cast<char>(cnt);
  }
  rep(i,H) cout << maze[i] << endl;
  return 0;
}

Measured memory_bytes: 256
def main():
    S = input()
    no_x = ''.join(S.split('x'))
    if no_x != no_x[::-1]:
        print(-1)
        return
    left, right = 0, len(S) - 1
    ans = 0
    while left <= right:
        if S[left] != S[right]:
            if S[left] == 'x':
                while S[left] != S[right]:
                    left += 1
                    ans += 1
            else:  # S[right] == 'x'
                while S[left] != S[right]:
                    right -= 1
                    ans += 1
        left += 1
        right -= 1
    print(ans)


if __name__ == '__main__':
    main()

Measured memory_bytes: 11096
from operator import itemgetter
import sys

input = sys.stdin.readline
inf = float('inf')

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

e = []
for _ in range(n):
    s, t, x = map(int, input().split())
    # 区間[s, t)に通行止め
    e.append((s - x, x, 0))  # 通行止め開始
    e.append((t - x - 0.5, x, 1))  # 通行止め解除
e.sort(key=itemgetter(0))

stop_set = set()
stop_at = inf
cur = 0
for _ in range(q):
    changed = False
    d = int(input())
    while cur < n * 2:
        exec_time, pos, typ = e[cur]
        if exec_time <= d:
            if typ == 0:
                stop_set.add(pos)
                if (not changed) and (pos < stop_at):
                    stop_at = pos
            else:
                stop_set.remove(pos)
                if (not changed) and (pos == stop_at):
                    changed = True
            cur += 1
        else:
            break

    if changed:
        if stop_set:
            stop_at = min(stop_set)
        else:
            stop_at = inf

    print(stop_at if stop_at != inf else -1)


Measured memory_bytes: 67316
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<P,int> PI;
typedef pair<P,P> PP;
#define rep(i,a,n) for(int i = a;i < n;i++)
#define LINF (ll)1e17
#define INF 1e9
#define MOD 1e9+7
#define sMOD 1e5
#define fs first
#define sc second

int main(){
	string s,t;
	int n,memo = 0;
	cin >> s >> n;
	vector<char> vec_c;
	vector<string> vec_s;
	
	rep(i,0,s.size()){
		vec_c.push_back(s[i]);
	}
	
	sort(vec_c.begin(),vec_c.end());
	
	rep(i,0,n){
		rep(j,0,s.size()){
			string t = "";
			if(s[j] == vec_c[i]){
				rep(k,j,min((int)s.size(),j+n)){
					t += s[k];
					vec_s.push_back(t);
				}
			}
		}
		
		sort(vec_s.begin(),vec_s.end());
		vec_s.erase(unique(vec_s.begin(),vec_s.end()), vec_s.end());
		
		
		if(vec_s.size() >= n){
			cout << vec_s[n-1] << endl;
			return 0;
		}
	}
	
	return 0;
}

Measured memory_bytes: 1660
import numpy as np

N = int(input())
A = list(map(int, input().split()))
A = np.int32(A)

vals, cnts = np.unique(A, return_counts=True)

if len(vals) == 1:
    print(0 if cnts[0] > 1 else 1)
elif vals[0] == 1:
    print(0 if cnts[0] > 1 else 1)
else:
    sat = np.ones(vals.max() + 1, dtype=int)
    for x in vals:
        sat[2 * x::x] = 0
    ans = ((sat[vals] == 1) & (cnts == 1)).sum().item()
    print(ans)

# 1
# 1
# 5
# 2 2 2 3 3
# 5
# 2 2 2 4 4
# 5
# 1 1 1 1 2

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

using namespace std;

inline void quit(){ exit(0); }

typedef long long ll;

ll mpow(ll _x, ll _y, ll _mod){
    if(_y==0) return 1;
    if(_y==1) return _x%_mod;
    if(_y&1) return (mpow(_x, _y-1, _mod)*_x)%_mod;
    ll _tmp = mpow(_x, _y>>1, _mod);
    return (_tmp*_tmp)%_mod;
}

int n, k;
bool chk[100002];
int inv;

int main(){
    scanf("%d %d", &n, &k);
    for(int i=1; i<=n; i++){
        char x;
        scanf(" %c", &x);
        chk[i] = x=='R';
    }
    for(int i=1; i<n; i++){
        if(chk[i] == chk[i+1]) inv++;
    }
    inv = min(inv+2*k, n-1);
    printf("%d", inv);
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define DEBUG(x) cerr << #x << ": " << (x) << endl;

int main() {
  int n, m;
  cin >> n >> m;
  int tot = 0;
  while (m--) {
    int x;
    cin >> x;
    tot += x;
  }
  if (tot > n) puts("-1");
  else printf("%d\n", n - tot);
}

Measured memory_bytes: 3764
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class mint:
    def __init__(self, x):
        self.__x = x % md

    def __str__(self):
        return str(self.__x)

    def __neg__(self):
        return mint(-self.__x)

    def __add__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x + other)

    def __sub__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x - other)

    def __rsub__(self, other):
        return mint(other - self.__x)

    def __mul__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * other)

    __radd__ = __add__
    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * pow(other, md - 2, md))

    def __rtruediv__(self, other):
        return mint(other * pow(self.__x, md - 2, md))

    def __pow__(self, power, modulo=None):
        return mint(pow(self.__x, power, md))

md = 10**9+7

def nCr(com_n, com_r):
    if com_n < com_r: return 0
    return fac[com_n] * ifac[com_r] * ifac[com_n - com_r]

n_max = 200005
fac = [mint(1)]
for i in range(1, n_max + 1): fac.append(fac[-1] * i)
ifac = [mint(1)] * (n_max + 1)
ifac[n_max] /= fac[n_max]
for i in range(n_max - 1, 1, -1): ifac[i] = ifac[i + 1] * (i + 1)

def main():
    n,a,b,c=MI()
    a, b = mint(a), mint(b)
    p=a/(a+b)
    pp=[mint(1)]
    for i in range(200005):pp.append(pp[-1]*p)
    q=b/(a+b)
    qq=[mint(1)]
    for i in range(200005):qq.append(qq[-1]*q)
    ans=0
    for m in range(n,2*n):
        ans+=m*100*(pp[n]*qq[m-n]+qq[n]*pp[m-n])*nCr(m-1,n-1)
    ans/=a+b
    print(ans)

main()

Measured memory_bytes: 169460
#include "bits/stdc++.h"
using namespace std;
const int maxn = 300300;
int main(){
    long long a, b;
    cin >> a >> b;
    if(b == 1 || a == b || a%b == 0) cout << -1 << endl;
    else{
      long long da = a;
      while(a%b == 0) a += da;
      cout << a << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<cstdio>
#include<cmath>
using namespace std;

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

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define mp1(a,b,c) P1(a,P(b,c))

const int INF=1000000000;
const int dir_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dir_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};

int main(){
	int cnt = 0;
	string s;
	cin >> s;
	rep(i,s.size()){
		if(cnt == 0 && s[i] == 'C')cnt ++;
		if(cnt == 1 && s[i] == 'F')cnt ++;
	}
	if(cnt == 2)puts("Yes");
	else puts("No");
}



Measured memory_bytes: 384
#include <iostream>
using namespace std;
int main(){
    int a,b,s=0;
    cin>>a>>b;
    if(a>b){
        s+=a;
        a--;
    }else{
        s+=b;
        b--;
    }
    s+=(a>b?a:b);
    cout<<s<<"\n";
}

Measured memory_bytes: 256
package main
import "fmt"

func main(){
	var H, W int64
	fmt.Scan(&H, &W)
	var ans int64
	if 2 <= H && 2 <= W {
		if H % 2 == 0 && W % 2 == 0{
			ans = H * W / 2
		}else if H % 2 == 1 && W % 2 == 1{
			ans = (H-1)*(W-1)/2 + (W-1)/2 + (H-1)/2 + 1
		}else if H % 2 == 1 {
			ans = (H-1) * W / 2 + W/2 
		}else if W % 2 == 1 {
			ans = H * (W-1) / 2 + H/2
		}
	}else if H == 1 || W == 1{
		ans = 1
	}
	fmt.Println(ans)
}

Measured memory_bytes: 512
N, M = map(int, input().split())
A = list(map(int, input().split()))

s_A = sorted(A, reverse=True)
sum_A = sum(A)
cnt = 0
for i in range(N):
    if(s_A[i] >= (1/(4*M))*sum_A):
        cnt += 1
print("Yes" if cnt >= M else "No")

Measured memory_bytes: 3064
#include <stdio.h>

int main(void)
{
	int i,j,k,l,a,b,c,d=0,n=0;
	int number[2000000];
	scanf("%d",&n);
	char order[12];
	

	
	for(i=0;i<n;i++){
		scanf("%s %d",order,&b);
		if(order[0]=='i') {
			number[i] = b;
		} else if(order[6] =='F') {
			i-=2;
			n-=2;
		} else if(order[6] =='L') {
			i--;
			n--;
			d++;
		} else {
			i--;
			n--;
			l=0;
			
			for(j=i;j>=0;j--) {
				if(l > 0) break;
				if(b==number[j]) {
					k = i-j;
					a=0;
					l++;
					while(k!=a++) {
						number[j+a-1] = number[j+a];
					}
					i--;
					n--;
				}
			}
		}
	}
	for(i=0; i < n-d;i++) {
		if(i==n-d-1) {
			printf("%d\n",number[n-1-i]);
		} else {
			printf("%d ",number[n-1-i]);
		}
	}
	return 0;
}
	
	
	



Measured memory_bytes: 5628
a,b,c,x,y = map(int, input().split())
one = max(x,y) * 2 * c
two = min(x,y) * 2 * c
if x >= y:
    two += abs(x-y) * a
else:
    two += abs(x-y) * b
three = x * a + y * b
print(min(one, two, three))

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
vector<int>g[110000];
int dp[110000];
int solve(int i)
{
	if(dp[i]!=-1)
		return dp[i];
	int ret=0;
	for(int j=0;j<g[i].size();j++)
	{
		ret=max(ret,solve(g[i][j])+1);
	}
	dp[i]=ret;
	return dp[i];
}
int main()
{
	int n,m;
	int u,v;
	cin>>n>>m;
	
	for(int i=0;i<m;i++)
	{
		cin>>u>>v;
		u--;
		v--;
		g[u].push_back(v);
	}
		for(int i=0;i<n;i++)
	{
		dp[i]=-1;
	}	
	int ret=0;
	for(int i=0;i<n;i++)
	{
		ret=max(ret,solve(i));
	}
	cout<<ret<<"\n";
	
}

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

class Program
{
    static void Main()
    {
        Console.WriteLine(Solve());
        //Solve();
        return;
    }

    public static string Solve()
    {
        int N = ReadInt();
        List<int[]> tasks = new List<int[]>(N);
        for (int i = 0; i < N; i++)
        {
            int[] input = ReadInts();
            tasks.Add(new int[] { input[0], input[1], input[1] - input[0] });
        }
        tasks.Sort((a, b) => a[1] - b[1]);
        int time = 0;
        for (int i = 0; i < N; i++)
        {
            //Console.WriteLine("[{0}]", string.Join(", ", tasks[i]));
            time += tasks[i][0];
            //Console.WriteLine(time);
            if (time > tasks[i][1])
            {
                return "No";
            }
        }
        return "Yes";
    }

    public static long Qu(long a, long b, long c)
    {
        long min, max;
        min = (a % c == 0) ? a / c : a / c + 1;
        max = b / c;
        return Math.Max(max - min + 1, 0);
    }

    public static long Lcm(long a, long b)
    {
        return a * b / Gcd(a, b);
    }

    public static long Gcd(long a, long b)
    {
        if (a < b)
            // 引数を入替えて自分を呼び出す
            return Gcd(b, a);
        while (b != 0)
        {
            var remainder = a % b;
            a = b;
            b = remainder;
        }
        return a;
    }

    private static string Read() { return Console.ReadLine(); }
    private static int ReadInt() { return int.Parse(Read()); }
    private static long ReadLong() { return long.Parse(Read()); }
    private static double ReadDouble() { return double.Parse(Read()); }
    private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
    private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
    private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }
}


Measured memory_bytes: 27812
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;   
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define sz(a) (ll)(a.size())
const int M = 3e5+5;
int rowCnt[M],colCnt[M];
vector<int> bombs[M];
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	int h,w,m;
	cin>>h>>w>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		rowCnt[x]++;
		colCnt[y]++;
		bombs[x].pb(y);
	}
	multiset<int> mlt;
	for(int i=1;i<=w;i++)
		mlt.insert(colCnt[i]);
	int ans = 0;
	for(int i=1;i<=h;i++)
	{
		for(auto u:bombs[i])
		{
			mlt.erase(mlt.find(colCnt[u]));
			colCnt[u]--;
			mlt.insert(colCnt[u]);
		}
		ans = max(ans, rowCnt[i]+*(--mlt.end()));
		for(auto u:bombs[i])
		{
			mlt.erase(mlt.find(colCnt[u]));
			colCnt[u]++;
			mlt.insert(colCnt[u]);
		}
	}
	cout<<ans<<"\n";
	return 0;
}

Measured memory_bytes: 36448
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>
const double EPS = 1e-9;
using namespace std;
class vector {
public:
	double x, y;
	vector(double a, double  b) {
		x = a;
		y = b;
	};
	vector operator * (const vector &v)const {
		return vector(x*v.x, y* v.y);
	}
	vector operator * (double a) {
		return vector(x * a, y * a);
	}
	vector operator - (vector v) {
		return vector(x - v.x, y - v.y);
	}
	vector operator + (vector v) {
		return vector(x + v.x, y + v.y);
	}
};
inline double dot(vector v1, vector v2) {
	return v1.x*v2.x + v1.y*v2.y;
}
inline double squ(vector v) {
	return v.x*v.x + v.y*v.y;
}
inline double norm(vector v) {
	return sqrt(squ(v));
}
inline void print(vector v) {
	printf("%.10f %.10f\n", v.x, v.y);
}
inline void printc(vector v1, vector v2) {
	printf("%.10f %.10f %.10f %.10f\n", v1.x, v1.y, v2.x, v2.y);
}
inline vector pro(vector base, vector v, vector be) {
	double a = dot(base, v) / squ(base);
	vector v1 = base * a;
	return v1 + be;
}
inline vector ref(vector v, vector be) {
	return (v - be)*2 + be;
}
inline double cross(vector v1, vector v2) {
	return v1.x*v2.y - v1.y*v2.x;
}
inline int ccw(vector v1, vector v2, vector v3) {
	vector a = v2 - v1;
	vector b = v3 - v1;
	if (cross(a, b) < 0.0) return -1;
	else if (cross(a, b) > 0.0) return 1;
	else if (dot(a, b) < 0.0) return -2;
	else if (dot(a, b) > squ(a)) return 2;
	else return 0;
}
inline int inter(vector v1, vector v2, vector v3, vector v4) {
	return (ccw(v1, v2, v3) * ccw(v1, v2, v4) <= 0) && (ccw(v3, v4, v1) * ccw(v3, v4, v2) <= 0);
}
inline double disPP(vector v1, vector v2) {
	return norm(v2 - v1);
}
inline double disLP(vector v1, vector v2, vector v3) {
	vector a = v2 - v1;
	vector b = v3 - v1;
	return fabs(cross(a, b) / norm(a));
}
inline double disSP(vector v1, vector v2, vector v3) {
	vector a = v2 - v1;
	vector b = v3 - v1;
	vector c = v1 - v2;
	vector d = v3 - v2;
	if (dot(a, b) < 0.0) return disPP(v1, v3);
	else if (dot(c, d) < 0.0) return disPP(v2, v3);
	else return disLP(v1, v2, v3);
}
inline double disSS(vector v1, vector v2, vector v3, vector v4) {
	if (inter(v1, v2, v3, v4)) return 0;
	double a = disSP(v1, v2, v3);
	double b = disSP(v1, v2, v4);
	double c = disSP(v3, v4, v1);
	double d = disSP(v3, v4, v2);
	return min(min(a, b), min(c, d));
}
inline vector getcross(vector v1, vector v2, vector v3, vector v4) {
	vector v5 = pro(v2 - v1, v3 - v1, v1);
	vector v6 = pro(v2 - v1, v4 - v1, v1);
	double a = disPP(v3, v5);
	double b = disPP(v4, v6);
	vector vans = (v6 - v5)*a*(1 / (a + b)) + v5;
	return vans;

}
int main() {
	int n, cx, cy, r,  x1, x2,y1, y2;
	cin >>cx >> cy >> r >>  n;
	vector o(cx, cy);
	for (int i = 0; i < n; i++) {
		cin >> x1 >> y1 >> x2 >> y2;
		vector v1(x1, y1);
		vector v2(x2, y2);
		vector ev = (v2 - v1)*(1 / norm(v2 - v1));
		vector pr = pro(v2 - v1, o - v1, v1);
		double l = sqrt(r *r - squ(o - pr));
		vector ans1 = ev * l + pr;
		vector ans2 = pr - ev * l;
		if (ans1.x > ans2.x) swap(ans1, ans2);
		else if (ans1.x == ans2.x)
			if (ans1.y > ans2.y) swap(ans1, ans2); 
		printc(ans1, ans2);
	}
	
	return 0;
}

Measured memory_bytes: 3208
using System;

namespace ABC131
{
    class Program
    {
        static void Main(string[] args)
        {
            string S = Console.ReadLine();
            char tmp = S[0];
            for (int i = 1; i < 4; i++)
            {
                if (tmp == S[i])
                {
                    Console.WriteLine("Bad");
                    return;
                }
                else
                {
                    tmp = S[i];
                }
            }
            Console.WriteLine("Good");
        }
    }
}


Measured memory_bytes: 11092
//#define DEB1 //input from input.txt
//#define NDEBUG
#include <iostream>
#include <algorithm>
#include <string>
#include <fstream>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <thread>
#include <mutex>
#include <iomanip>
#include <cassert>

#define ZERO(a) memset(a, 0, sizeof(a))
#define MINUS(a) memset(a, 0xff, sizeof(a))
#define INF(a) memset(a, 0x3f, sizeof(a))
#define ALL(t) (t).begin(),(t).end()
#define FILL(a,c) fill(a, a+ sizeof(a)/sizeof(*a),c)
#define FILL2D(A,c) fill(A[0], A[0] +sizeof(A)/sizeof(**A),c)
#define FILL3D(A,c) fill(A[0][0], A[0][0] +sizeof(A)/sizeof(***A),c)
#define REP(i,m) for(int i=0;i<(m);++i)
// closed interval, inverse repeat
#define CIREP(i,start,fin) for(int i=(start);i>=(fin);i--)
#define CREP(i,start,fin) for(int i=(start);i<=(fin);i++)
#define RNG(i,start,fin) for(int i=(start);i<(fin);i++)
#define IN(a, x, b) (a<=x && x<b)
#define PB push_back
#define SZ(x) (int)(x).size()

using namespace std;

using LL = long long;
using PAIR = pair<int, int>;
using PAIRLL = pair<LL,LL>;
using VI = vector<int>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VVI = vector<VI>;
const LL LINF = 1001002003004005006ll;
/* 
template<typename T>inline istream& operator>>(istream&i,vector<T>&v)
{REP(j,SZ(v))i>>v[j];return i;}

template<typename T>string join(const vector<T>&v)
{stringstream s;REP(i,SZ(v))s<<' '<<v[i];return s.str().substr(1);}

template<typename T>inline ostream& operator<<(ostream&o,const vector<T>&v)
{if(SZ(v))o<<join(v);return o;}
*/

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




/*
constant values
*/

//const int dx[] = {1,0,-1,0};
//const int dy[] = {0,1,0,-1};
//const int MX = 31001;

//const ll INF= 1LL<<60 ;//INF = 1001001001001; //1e9


// Main program
void solve(){
    char c;
    cin >> c;
    string S = "abcdefghijklmnopqrstuvwxyz";
    cerr << S.size();
    REP(i,25){
        if(S[i]==c){
            cout << S[i+1] << endl;
        }
    }

    return;
}



// ----------------------------------------------
int main(){

#ifdef DEB1
    cout << "DEBUG MODE"  << endl;
    ifstream in("input.txt"); //for debug
    cin.rdbuf(in.rdbuf()); //for debug
#endif

    int T=1; 

    for (int i = 0; i < T; ++i) {
        solve();
    }

    return 0;
}

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

int main() {
    int n;cin>>n;
    vector<int>dp(3,0);
    for (int i = 0; i < n; ++i) {
        vector<int>a(3),temp(3,0);
        for (int j = 0; j < 3; ++j) {
            cin>>a[j];
        }
        for (int k = 0; k < 3; ++k) {
            for (int j = 0; j < 3; ++j) {
                if (k != j)
                    temp[j] = max(temp[j] , dp[k] + a[j]);
            }
        }
        dp = temp;
    }
    cout<<*max_element(dp.begin(),dp.end())<<'\n';
    return 0;
}

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

using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> a(n+1, 0);
	for (int i = 1; i < n; i++) {
		int x;
		cin >> x;
		a[x]++;
	}
	for (int i = 1; i < (int)a.size(); i++) {
		cout << a[i] << "\n";
	}

	return 0;
}

Measured memory_bytes: 3996
import Control.Applicative
import Control.Monad
import Data.List
 
main = do
  n <- readLn
  xs <- replicateM n getLine
  putStr . sort . foldl1 f $ xs
 
f (x:xs) ys
  | x `elem` ys = (x :) . f xs . delete x $ ys
  | otherwise = f xs ys
f _ _ = []

Measured memory_bytes: 1020
#include<stdio.h>
int main()
{
	int S;
	scanf("%d",&S);
	if((S%10)==(((S-(S%10))/10)%10))

		printf("Bad\n");

        else if(((S%100)/10)==(((S-((S%100)/10))/100)%10))

		printf("Bad\n");

        else if(((S/100)%10)==(S/1000))

		printf("Bad\n");
	else
		printf("Good\n");

	return 0;
}


Measured memory_bytes: 128
n = int(input())
A = [int(i) for i in input().split()]
cnt_x = [0] * (10**5 + 2)
for a in A:
    cnt_x[a - 1] += 1
    cnt_x[a] += 1
    cnt_x[a + 1] += 1
print(max(cnt_x))

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

int N,M;
vector<int> s,c;

bool ok(string str){
  if(str.size() !=N) return false;
  for(int i=0;i<M;i++) if(str[s[i]]!=(char)(c[i]+'0')) return false;
  return true;
}

string solve() {
  for(int i=0;i<1000;i++){
    stringstream iss; iss << i;
    string str = iss.str();
    if(ok(str)) return str;
  }
  return "-1";
}
int main() {
  cin>> N >> M;
  s.resize(M); c.resize(M);
  for(int i=0;i<M;i++) cin >> s[i] >> c[i], s[i]--;
  cout << solve() << endl;
}

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[] a = new int[n];
      int[] b = new int[n];
      int[] c = new int[n-1];
      int sum = 0;
      for(int i = 0;i < n;i++)a[i]=sc.nextInt();
      for(int i = 0;i < n;i++)b[i]=sc.nextInt();
      for(int i = 0;i < n-1;i++)c[i]=sc.nextInt();
      for(int i = 0;i < n;i++){
      	int x = a[i];
        sum += b[x-1];
      }
      for(int i = 0;i < n-1;i++){
      	if(a[i+1]-a[i]==1)sum += c[a[i]-1];
      }
      System.out.println(sum);
    }
    public static int lcm(int x, int y){
      return x*y/gcd(x,y);
    }
    public static int gcd(int x, int y){
      if(x < y)return gcd(y,x);
      if(y==0)return x;
      return gcd(y,x%y);
    }
}


Measured memory_bytes: 21588
#define ONLINE_JUDGE
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vp;
const ll INF=1001001001;
const ll LINF=1001001001001001001;
const ll D4[]={0,1,0,-1,0};
const ll D8[]={0,1,1,0,-1,-1,1,-1,0};
#define _overload3(_1,_2,_3,name,...) name
#define _rep2(i,n) for(ll i=0;i<(n);++i)
#define _rep3(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(...) _overload3(__VA_ARGS__,_rep3,_rep2)(__VA_ARGS__)
#define _repe2(i,n) for(ll i=0;i<=(n);++i)
#define _repe3(i,a,b) for(ll i=(a);i<=(b);++i)
#define repe(...) _overload3(__VA_ARGS__,_repe3,_repe2)(__VA_ARGS__)
#define _rrep2(i,n) for(ll i=(n)-1;i>=0;i--)
#define _rrep3(i,a,b) for(ll i=(b)-1;i>=(a);i--)
#define rrep(...) _overload3(__VA_ARGS__,_rrep3,_rrep2)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
template<class T>
bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>
bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
template<class T>
using pq=priority_queue<T,vector<T>,greater<T>>;

void solve();

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

void solve(){
    ll h,w,a,b;cin>>h>>w>>a>>b;
    vvl ans(h,vl(w));
    rep(i,h){
        rep(j,w)ans[i][j]=(j<a)^(i<b);
    }

    rep(i,h){
        rep(j,w)cout<<ans[i][j];
        cout<<endl;
    }
}

Measured memory_bytes: 9088
import Control.Monad
import Data.Maybe
import Data.List
import qualified Data.ByteString.Char8 as BS

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getIntList = readIntList <$> BS.getLine

main :: IO ()
main = do
    [n, k] <- getIntList
    prices <- getIntList

    let total = sum $ take k $ sort prices 

    print total

Measured memory_bytes: 4532
n, x = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
for i in range(n-1):
    ans += max(0, a[i] + a[i+1] - x)
    if a[i]+a[i+1]<=x: continue
    if a[i]>x: a[i+1]=0
    else: a[i+1] = x - a[i]
print(ans)

Measured memory_bytes: 14252
# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    A = np.array(sorted(list(map(int, args[1].split()))))
    F = np.array(sorted(list(map(int, args[2].split())), reverse=True))

    right = 1+A[-1]*F[0]
    left = -1

    total = A.sum()
    while left+1 < right:
        mid = (left+right)//2
        if total - np.minimum(A, mid//F).sum() <= k:
            right = mid
        else:
            left = mid

    return str(right)


if __name__ == "__main__":
    print(solve(*(open(0).read().split('\n'))))


Measured memory_bytes: 37588
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define SZ(i) int(i.size())
#ifdef tmd
#define IOS()
#define debug(...) fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define debug(...)
#endif

const int MAXN = 200005;
const ll MOD = 1000000007;

int n, m, cnt[MAXN];
/*********************GoodLuck***********************/
int main () {
    IOS();

    cin >> n >> m;
    REP (i, m) {
        int u, v;
        cin >> u >> v;
        if (v == 1 || v == n) {
            cnt[u]++;
        }
        if (u == 1 || u == n) {
            cnt[v]++;
        }
    }

    bool ans = false;
    for (int i=2; i<n;i++) {
        ans |= cnt[i] == 2;
    }

    cout << (ans ? "POSSIBLE" : "IMPOSSIBLE") << endl;
    return 0;
}


Measured memory_bytes: 1024
n,m = map(int,input().split())
drinks = []
cost = 0
flag = True
for i in range(n):
    a,b = map(int,input().split())
    drinks.append((a,b))
drinks.sort(reverse = True)
while m:
    x = drinks.pop()
    num = min(m,x[1])
    cost += num * x[0]
    m -= num 
print(cost)

Measured memory_bytes: 16892
#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<set>
using namespace std;

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define VSORT(v) sort(v.begin(), v.end());
#define pb(a) push_back(a)


typedef long long ll;

typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int INF = 1e9 + 7;

#define ARRAY_MAX 100005

template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }
template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
	for (auto& e : t) fill_v(e, v);
}


int main() {

	int n;
	cin >> n;
	vector<int> x(n), y(n), h(n);
	int height = 1;

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

			height = i;
		}
	}

	for (int yy = 0; yy <= 100; yy++)
	{
		for (int xx = 0; xx <= 100; xx++)
		{
			//中心座標を(y,x)に決める
			int diff_x = abs(xx - x[height]);
			int diff_y = abs(yy - y[height]);
		
			int h_tmp = h[height] + diff_x + diff_y;//頂点の高さを決め打ち

			bool exist = true;
			for (int i = 0; i < n; i++)
			{
				if (h[i] != max(h_tmp - abs(xx - x[i]) - abs(yy - y[i]), 0))
				{
					exist = false;
					break;
				}
			}
			if (exist)
			{
				cout << xx << " " << yy << " " << h_tmp << endl;
				return 0;
			}
		}
	}


}

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

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int N,M;
int A[1111],B[1111],C[1111];

const int INF=1001001001001001001ll;
int D[111][111];

signed main(){
    cin>>N>>M;
    rep(i,M)cin>>A[i]>>B[i]>>C[i],A[i]--,B[i]--;


    fill_n(*D,111*111,INF);
    rep(i,N)D[i][i]=0;
    rep(i,M){
        chmin(D[A[i]][B[i]],C[i]);
        chmin(D[B[i]][A[i]],C[i]);
    }

    rep(k,N)rep(i,N)rep(j,N)chmin(D[i][j],D[i][k]+D[k][j]);


    int ans=0;
    rep(i,M){
        bool ok=true;
        rep(j,N)rep(k,N)if(D[j][A[i]]+C[i]+D[B[i]][k]==D[j][k]||D[j][B[i]]+C[i]+D[A[i]][k]==D[j][k])ok=false;
        if(ok)ans++;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 384
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache, reduce
from math import ceil, floor

import heapq
import itertools
import operator


def get_int():
    return int(input())


def get_str():
    return input().strip()


def get_int_list():
    return [int(i) for i in input().split()]


def get_char_list():
    return list(input().strip())


def main():
    n, a, b = get_int_list()
    max_ = min(a, b)
    min_ = max(0, a + b - n)
    print("{} {}".format(max_, min_))


if __name__ == '__main__':
    main()


Measured memory_bytes: 3828
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define repr(i,n) for(ll i=(n-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define br cout << "\n";
using namespace std;
const long long INF = 1e10;
const long long MOD = 1e9+7;
using Graph = vector<vector<ll>>;
using pll = pair<ll, ll>;
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;}

// 0 false, 1 true 
// string to int : -48
// a to A : -32
// ceil(a)  1.2->2.0
// c++17	g++ -std=c++17 a.cpp

int main() {
    std::cout << std::fixed << std::setprecision(15);
    ll m; cin >> m;
    ll keta = 0;
    ll num = 0;
    rep(i, m){
        ll d, c; cin >> d >> c;
        num += d * c;
        keta += c;
    }

    ll ans = 0;
    ans += keta - 1;
    
    if(num % 9 == 0){
        ans += (num / 9) - 1;
    }else{
        ans += num / 9;
    }

    cout << ans << endl;

}

Measured memory_bytes: 3624
#include<stdio.h>

int main(){
    int i, count = 0;
    int block, cost, hear, res;
    int a[100];

    scanf("%d%d%d",&block,&cost,&hear);
    for(i = 0;i < cost;i++){
        scanf("%d",&a[i]);
    }

    do{
    for(i = 0; i <= block; i++){
        if(hear == a[i]) count++;
    }
    hear++;
    }while(hear < block);

    res = count < cost - count ? count : cost-count < 0 ? 0 : cost-count;
    printf("%d",res);

    return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<string>
using namespace std;
int main() {
	int n, w[100], x = 0, y = 0, z = 100000000;
	cin >> n;
	for (int a = 0; a < n; a++) {
		cin >> w[a];
		x = w[a] + x;
	}
	for (int i = 0; i < n; i++) {
		y = w[i] + y;
		if (y >= x - y) {
			if (z > y-(x-y))z =y-(x-y);
		}
		if (y <= x - y) {
			if (z >(x-y)-y)z = (x-y)-y;
		}
	}
	cout << z << endl;
	return 0;
}


Measured memory_bytes: 256
x, y, z, k = map(int, input().split())
a = sorted(list(map(int, input().split())),reverse=True)
b = sorted(list(map(int, input().split())),reverse=True)
c = sorted(list(map(int, input().split())),reverse=True)
def search(a, b):
  ret = []
  al = len(a)
  bl = len(b)
  for i in range(min(al, k)):
    for j in range(min(bl, k-i)):
      ret.append(a[i] + b[j])
  ret.sort(reverse = True)
  return ret
d = search(a, b)      
e = search(c, d)    

for i in range(k):
  print(e[i])

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

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

constexpr int atcoder_mod = 1e9+7;

using namespace std;
using ll = long long;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

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

	while(true){
		int N=in();
		if(!N) break;
		double ave=0,ave2=0;
		REP(i,N){
			int v=in();
			ave += v;
			ave2 += v*v;
		}
		ave /= N;
		ave2 /= N;

		printf("%.10lf\n",sqrt(ave2-ave*ave));
	}
		
	return 0;
}



Measured memory_bytes: 3140
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc=new Scanner(System.in);

		while(sc.hasNext()){
			int n=sc.nextInt();
			int a[]=new int [n];
			long dp[][]=new long[n][21];

			for(int i=0; i<n; i++){
				a[i]=sc.nextInt();
			}
			for(int i=0; i<n; i++){
				Arrays.fill(dp[i], 0);
			}
			dp[0][a[0]]=1;

			for(int i=1; i<n-1; i++){
				for(int j=0; j<=20; j++){
					if(0 <= j-a[i]  && dp[i-1][j-a[i]] > 0){
						dp[i][j]+=dp[i-1][j-a[i]];
					}
					if(j+a[i] <= 20 && dp[i-1][j+a[i]] > 0){
						dp[i][j]+=dp[i-1][j+a[i]];
					}

				}
			}

			System.out.println(dp[n-2][a[n-1]]);
		}
	}

}

Measured memory_bytes: 18116
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

template<typename T>
T assignment(vector<vector<T>> &v){
    int n = v.size(), m = v[0].size();
    vector<T> pot(m), A(m);
    vector<int> id(m), prv(m);
    vector<int> l(n, -1), r(m, -1);
    iota(id.begin(),id.end(), 0);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) A[j] = v[i][j] - pot[j], prv[j] = i;
        int o = 0, j = 0;
        T w = 0;
        [&](){
            int s = 0, t = 0;
            while(true){
                if(s == t){
                    o = s;
                    w = A[id[t++]];
                    for (int k = t; k < m; ++k) {
                        j = id[k];
                        T h = A[j];
                        if(h <= w){
                            if(h < w) t = s, w = h;
                            id[k] = id[t]; id[t++] = j;
                        }
                    }
                    for (int k = s; k < t; ++k) {
                        j = id[k];
                        if(!~r[j]) return;
                    }
                }
                int q = id[s++], x = r[q];
                for (int k = t; k < m; ++k) {
                    j = id[k];
                    T h = v[x][j]-v[x][q]-(pot[j]-pot[q])+w;
                    if(h < A[j]){
                        A[j] = h; prv[j] = x;
                        if(h == w){
                            if(r[j] < 0) return;
                            id[k] = id[t]; id[t++] = j;
                        }
                    }
                }
            }
        }();
        for (int k = 0; k < o; ++k) {
            pot[id[k]] += A[id[k]]-w;
        }
        int x;
        do {
            r[j] = x = prv[j];
            swap(j, l[x]);
        } while(i != x);
    }
    T res = 0;
    for (int i = 0; i < n; ++i) res += v[i][l[i]];
    return res;
}

int main() {
    int n, m;
    while(cin >> n >> m, n){
        vector<int> v(n), u(m);
        for (auto &&i : v) scanf("%d", &i);
        for (auto &&j : u) scanf("%d", &j);
        if(n > m) swap(n, m), swap(v, u);
        vector<vector<int>> A(n, vector<int>(m, 0));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                A[i][j] = -abs(v[i]-u[j])*(abs(v[i]-u[j])-30)*(abs(v[i]-u[j])-30);
            }
        }
        cout << -assignment(A) << "\n";
    }
    return 0;
}


Measured memory_bytes: 3228
pub fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

pub fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

pub fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

pub fn read_col<T: std::str::FromStr>(n: u32) -> Vec<T> {
    (0..n).map(|_| read()).collect()
}

fn main() {
    let v: Vec<String> = read_vec();
    let a: Vec<char> = v[0].chars().collect();
    let b: Vec<char> = v[1].chars().collect();
    let c: Vec<char> = v[2].chars().collect();

    if a[a.len() - 1] == b[0] && b[b.len() - 1] == c[0] {
        println!("YES");
    } else {
        println!("NO");
    }
}


Measured memory_bytes: 4352
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
n,m=map(int,input().split())
A=[int(input()) for i in range(m)]
NG=[0]*(10**5+10)
for i in A:
    NG[i]=1


@lru_cache(maxsize=10**10)
def qwe(x):
    if x==n:return 1
    if x>n:return 0
    if NG[x+1] and NG[x+2]: print(0);exit()
    if NG[x+1]:return qwe(x+2)%mod
    if NG[x+2]:return qwe(x+1)%mod
    return (qwe(x+2)+qwe(x+1))%mod
print(qwe(0))
    


Measured memory_bytes: 78480
#include <stdio.h>

int main() {
  int n, i;
  scanf("%d", &n);
  int T[n+1];
  for (i=0; i<n; i++) {
    scanf("%d", &T[i]);
  }

  int m, p, x;
  scanf("%d", &m);
  for (i=0; i<m; i++) {
    scanf("%d %d", &p, &x);
    T[n]=T[p-1];
    T[p-1]=x;

    int sum=0, j;
    for (j=0; j<n; j++) {
      sum+=T[j];
    }
    printf("%d\n", sum);
    T[p-1]=T[n];
  }
  return 0;
}

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

typedef struct{
  int data;
}dice;

int main(void)
{
  int i;
  int da[5];
  char move[101];
  int length; //???????????????
  dice temp_a;
  dice temp_b;

  for(i=0; i<6; i++){
    scanf("%d",&da[i]);
  }
  
  dice one[6] = {
    {da[0]}, //?????????????????°???
    {da[1]},
    {da[2]},
    {da[3]},
    {da[4]},
    {da[5]},
  };

  scanf("%s",move);
  length = (int)strlen(move);

  for(i=0; i<length; i++){
    if(move[i] == 'E'){
      temp_a = one[2]; //??????temp_a???
      one[2] = one[0]; //?????????
      temp_b = one[5]; //??????temp_b???
      one[5] = temp_a; //???(temp_a)??????
      temp_a = one[3]; //??????temp_a???
      one[3] = temp_b; //???(temp_b)??????
    }
    else if(move[i] == 'N'){
      temp_a = one[4];
      one[4] = one[0]; //?????????
      temp_b = one[5];
      one[5] = temp_a; //?????????
      temp_a = one[1];
      one[1] = temp_b; //?????????
    }
    else if(move[i] == 'S'){
      temp_a = one[1];
      one[1] = one[0]; //?????????
      temp_b = one[5];
      one[5] = temp_a; //?????????
      temp_a = one[4];
      one[4] = temp_b; //?????????
    }
    else if(move[i] == 'W'){
      temp_a = one[3];
      one[3] = one[0]; //?????????
      temp_b = one[5];
      one[5] = temp_a; //?????????
      temp_a = one[2];
      one[2] = temp_b; //?????????
    }
    one[0] = temp_a; //??±?????????
  }

  printf("%d\n",one[0].data);
    
  return(0);
}

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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
//#pragma GCC optimize ("-O3") 
#ifdef YANG33
#include "mydebug.hpp"
#else
#define DD(x) 
#endif
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2019/02/27  Problem: ABC 114 A / Link: http://abc114.contest.atcoder.jp/tasks/abc114_a  ----- */
/* ------問題------



-----問題ここまで----- */
/* -----解説等-----



----解説ここまで---- */

LL ans = 0LL;

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

	int N; cin >> N;
	if (N == 3 || N == 5 | N == 7) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <set>
#define ll long long
#define ld long double
#define pb push_back
#define mk make_pair
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
using namespace std;

int main(){
    ll n;
    string s;
    cin >> n;
    set <string> ar;
    for(ll i = 0;i<n;i++){
        cin >> s;
        ar.insert(s);
    }
    cout << ar.size();
}


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

  char a[N];
  int s[N];
int main()
{
  scanf("%s",a);
  for (int i=strlen(a);~--i;)
    s[a[i]]=1;
  if (s['N']==s['S']&&s['W']==s['E'])
    puts("Yes");
  else
    puts("No");
  exit(0);
}

Measured memory_bytes: 256