akhauriyash/Code-Regression huggingface dataset:
import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array

# 時々使う
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)


# MOD = 10 ** 9 + 7
MOD = 998244353
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()
    left = [0] * (N + 1)
    right = [0] * (N + 1)

    # 予めGCDを計算する
    for i in range(N):
        left[i+1] = math.gcd(left[i], A[i])
    for i in reversed(range(N)):
        right[i] = math.gcd(right[i+1], A[i])

    ret = 0
    for i in range(N):
        ret = max(ret, math.gcd(left[i], right[i+1]))
    print(ret)


if __name__ == '__main__':
    main()


Measured memory_bytes: 21768
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define rep2(i,n) for(int i = 1; i <= (n); ++i)
#define rrep2(i,n) for(int i = (n); i > 0; --i)
#define srep(i,s,n) for(int i = s; i < (n); ++i)
#define rsrep(i,s,n) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<(x)<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define show_pair(...) cout<<#__VA_ARGS__<<" = "<<endl; for (const auto& x : (__VA_ARGS__)) { cout<<"  "<<x.fi<<" : "<<x.se<<endl; }
#define out_ary(...) { int n = (__VA_ARGS__).size(); rep(i, n) printf("%d%s", (__VA_ARGS__)[i], i != n-1 ? " " : "\n"); }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<P> vpair;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vll> vvll;
typedef vector<vstr> vvstr;
typedef vector<vbool> vvbool;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;


bool calc(int i, int j) { return (i&(1<<j)); }

int main() {
    int n;
    cin >> n;
    vint a(n);
    vint x[n];
    vbool y[n];
    rep(i, n) {
        cin >> a[i];
        rep(j, a[i]) {
            int xi, yi;
            cin >> xi >> yi;
            xi--;
            x[i].push_back(xi);
            if (yi) y[i].push_back(true);
            else y[i].push_back(false);
        }
    }

    int ans = 0;
    rep(i, 1<<n) {
        vbool t(n);
        rep(j, n) t[j] = calc(i, j);
        int num = 0;
        rep(j, n) num += t[j];
        if (num <= ans) continue;
        bool c = true;
        rep(j, n) {
            if (t[j] == false) continue;
            rep(k, a[j]) if (t[x[j][k]] != y[j][k]) c = false;
            if (c == false) break;
        }
        if (c) ans = max(ans, num);
    }

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

Measured memory_bytes: 256
using System;
using System.Linq;
class Program
{
	static void Main(string[] args)
	{
		string input = Console.ReadLine();
		//int n = int.Parse(input[0]);
        long sum = 0;
        for (int bit = 0; bit < (1 << input.Length-1); ++bit){
            string input2 = input;
            System.Text.StringBuilder sb = new System.Text.StringBuilder(input2);
            int count = 0;
            for (int i = 0; i < input.Length; i++) {
                if ((bit & (1 << i)) == (1 << i)) {
                    sb.Insert(i+1+count, "+");
                    count++;
                }
            }
            //Console.WriteLine(sb.ToString());
            string[] array = sb.ToString().Split('+');
            long[] longArray = new long[array.Length];
            for(int i = 0; i < array.Length; i++) {
            	longArray[i] = long.Parse(array[i]);
            }
            sum += longArray.Sum();
            //Console.WriteLine(intArray.Sum());
        }
        Console.WriteLine(sum);
	}
}

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

int main(){
 	int N,K;
  	cin >> N >> K;
  	vector<int> tree(N);
  	for(int i=0; i < N; ++i)
      	cin >> tree.at(i);
  
  	sort(tree.begin(), tree.end());
  	int ans = 1000000000;
  	for(int i=0; i < N-K+1; ++i){
      	int diff;
      	diff=tree.at(i+K-1)-tree.at(i);
      	if(diff<ans){
         	ans=diff; 
        }
    }
  	cout << ans << endl;
}	

Measured memory_bytes: 640
a[1<<18],b[1<<18],c[1<<18];i;f;
main(n,m){
for(scanf("%d%d",&n,&m);~scanf("%d%d",a+i,b+i);i++)a[i]-1||++c[b[i]];
for(i=0;i<m;i++)b[i]-n||(f|=c[a[i]]);
printf("%sPOSSIBLE",f?"":"IM");
}

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

int main() {
  int64_t X;
  cin>>X;
  int64_t i=0;
  int64_t T=100;
  bool finished =true;
  while(finished){
    i++;
    T*=1.01;
    if(T>=X){
    cout<< i;
    finished=false;
    }
  }
}
  
    
 


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
 
#define P(p) cout<<(p)<<endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.begin(), v.end(),greater<int>());
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return
#define lb(v,n) lower_bound(v.begin(),v.end(),n)
#define ub(v,n) upper_bound(v.begin(),v.end(),n)
#define mae(v) max_element(v.begin(),v.end())
#define mie(v) min_element(v.begin(),v.end())
#define INF 0x7FFFFFFF
#define mod 1000000007
typedef long long ll;
////////////////////////////////////////////////////////////

int main(){
	vector<int> v(3);
	cin >> v[0] >> v[1] >> v[2];
	vsort(v);
	cout << v[2]*10+v[1]+v[0] << endl;

	ret 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

int main(){
	
	int H, W, h, w;
	
	cin >> H >> W >> h >> w;
	
	if(H % h == 0 && W % w == 0){
		cout << "No" << endl;
		return 0;
	}
	
	cout << "Yes" << endl;
	
	for(int i = 1; i <= H; i++){
		for(int j = 1; j <= W; j++){
			if(i % h == 0 && j % w == 0){
				cout << -((h * w - 1) * 1000 + 1);
			}else{
				cout << 1000;
			}
			if(j != W){
				cout << " ";
			}
		}
		cout << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1536
#include <stdio.h>


typedef struct{
	char name[11];
	int time;
}DATA_T;


int main()
{
	char in_str[30];
	int n, q;
	DATA_T *process;
	int *ring_queue;
	int head, end;
	int time;
	int i, j;


	fgets(in_str, sizeof(in_str), stdin);
	sscanf(in_str, "%d %d", &n, &q);

	process = (DATA_T *)malloc(sizeof(DATA_T) * n);
	ring_queue = (int *)malloc(sizeof(int) * (n + 1));

	for(i = 0; i < n; i++){
		fgets(in_str, sizeof(in_str), stdin);
		sscanf(in_str, "%s %d", &process[i].name, &process[i].time);
	}

	for(i = 0; i < n; i++)
		ring_queue[i] = i;


	head = time = 0;
	end = n;
	// キューが空になるまで処理をする
	while(head != end){
		if(process[ring_queue[head]].time - q > 0){
			process[ring_queue[head]].time -= q;
			time += q;
			ring_queue[end] = ring_queue[head];
			end = (end + 1) % (n + 1);
			head = (head + 1) % (n + 1);
		}else{
			time += process[ring_queue[head]].time;
			printf("%s %d\n", process[ring_queue[head]].name, time);
			head = (head + 1) % (n + 1);
		}
	}

	return 0;
}


Measured memory_bytes: 2672
from collections import defaultdict
N, M = map(int, input().split())
A = [int(input()) for i in range(M)]
dict = defaultdict(int)
for a in A:
    dict[a] += 1

mod = 10 ** 9 + 7
dp = [0 for _ in range(N+1)]
dp[0] = 1
dp[1] = 1
for i in range(1, N):
    if dict[i] == 0 and dict[i-1] == 0:
        dp[i+1] += ((dp[i-1] + dp[i]) % mod)
    elif dict[i] == 0:
        dp[i+1] += (dp[i] % mod)
    elif dict[i-1] == 0:
        dp[i+1] += (dp[i-1] % mod)

print(dp[-1])

Measured memory_bytes: 18960
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main(void){
  int n;
  int i,j,k;
  int tmp;
  int ans=0;
  scanf("%d",&n);

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

      }
    }

  printf("%d",ans);
return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    string s;
    cin >> s;
    
    bool flag = true;
    if(s[0] != 'A')
    {
        flag = false;
    }

    int cnt = 0;
    for(int i = 2; i < s.size() - 1; i++)
    {
        if(s[i] == 'C')
        {
            cnt++;
        }
    }
    
    if(cnt != 1)
    {
        flag = false;
    }
    
    int cnt2 = 0;
    for(int i = 0; i < s.size(); i++)
    {
        if(s[i] >= 'A' && s[i] <= 'Z')
        {
            cnt2++;
        }
    }
    
    if(cnt2 != 2)
    {
        flag = false;
    }
    
    if(flag == true)
    {
        cout << "AC" << endl;
    }
    else
    {
        cout << "WA" << endl;
    }
    
    return 0;
}

Measured memory_bytes: 256
package main

import "fmt"

const (
	xmax = 200000
)

func main() {
	var X int
	fmt.Scanf("%d", &X)
	f := make([]bool, xmax+1)
	for i := 2; i <= xmax; i++ {
		f[i] = true
	}
	for i := 4; i <= xmax; i += 2 {
		f[i] = false
	}
	for i := 3; i <= xmax; i += 2 {
		if !f[i] {
			continue
		}
		j := i + i
		for j <= xmax {
			f[j] = false
			j += i
		}
	}
	for i := X; i <= xmax; i++ {
		if f[i] {
			fmt.Println(i)
			return
		}
	}

}


Measured memory_bytes: 768
from math import pow, cos, radians, sqrt

a, b, h, m = tuple(map(int, input().split()))

angle_h = 360 * (h / 12) + 30 * (m / 60)
angle_m = 360 * (m / 60)
angle = abs(angle_h - angle_m)
angle = angle if angle <= 180 else 360 - angle

ans = pow(a, 2) + pow(b, 2) - 2 * a * b * cos(radians(angle))
print(sqrt(ans))


Measured memory_bytes: 9416
package main

import "fmt"

func main() {
	var M, D int
	var d1, d10 int
	out := 0
	fmt.Scanf("%d %d", &M, &D)
	for i := 1; i <= M; i++ {
		for ii := 1; ii <= D; ii++ {
			d1 = ii % 10
			d10 = ii / 10
			if d1*d10 == i && d1 > 1 && d10 > 1 {
				out++
			}
		}
	}
	fmt.Println(out)
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
        using namespace std;
   #define int long long
    const int MAX =200002;
const int MOD =1000000007;
    map<pair<int,int>,int>mp;
    int solve(int a,int b){
        if(a==b)return 1;
        if(mp.find({a,b})!=mp.end())return mp[{a,b}];
        return mp[{a,b}]=solve((a>>1)+(a&1),(b>>1))+solve((a>>1),(b>>1))-(((b&(b-1))>>1)<(a>>1));
    }
     signed main(){
     int a,b;
     cin>>a>>b;
    cout<<solve(a,b)<<endl;
    //for(auto&& i:mp)cerr<<i.first.first<<' '<<i.first.second<<' '<<i.second<<endl;

     }


 


 






    





      

        


Measured memory_bytes: 3644
// Hint: Don't look, No need, Let'em Play.

#pragma optimize("O2")
#include <bits/stdc++.h>
#include "bits/stdc++.h"

using namespace std;

#define int long long
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

#ifndef bhupixb
    #define var(...)
    #define stl(...)
#endif

void solve() {
    int x;
    for (int i = 1; i <= 5; ++i) {
        cin >> x;
        if (x == 0) {
            cout << i << '\n';
            return;
        }
    }
}

signed main() {
    fast;
    int t = 1; //cin >> t;
    while (t--) {
        solve();
    }


  return 0;
}

Measured memory_bytes: 3632
#include<stdio.h>
#include<iostream>

using namespace std;

int main()
{
	int n;
	int flag = 0;
	cin>>n;
	int t1=0,x1=0,y1=0;
	while(n--)
	{
		int t,x,y;
		cin>>t>>x>>y;
		if((t-t1-x+x1-y+y1)>=0 && (t-t1-x+x1-y+y1)%2 == 0) continue;
		else flag = 1;
		t1 = t;
		x1 = x;
		y1 = y;	
	}	
	if(flag == 1) cout<<"No";
	else cout<<"Yes";
} 

Measured memory_bytes: 256
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    ArrayList<String> S = new ArrayList<String>();
    ArrayList<String> T = new ArrayList<String>();
    int N = sc.nextInt();
    for(int i=0;i<N;i++){
      String s = sc.next();
      S.add(s);
    }
    int M = sc.nextInt();
    for(int i=0;i<M;i++){
      String t = sc.next();
      T.add(t);
    }
    HashMap<String,Integer> map = new HashMap<String,Integer>();

    for(int i=0;i<N;i++){
      if(map.containsKey(S.get(i))) map.put(S.get(i),(map.get(S.get(i)).intValue()+1));
      else map.put(S.get(i),1);
    }
    for(int i=0;i<M;i++){
      if(map.containsKey(T.get(i))) map.put(T.get(i),map.get(T.get(i)).intValue()-1);
    }

    ArrayList<Integer> coll = new ArrayList<Integer>(map.values());

    Integer ii = Collections.max(coll);
		System.out.println((ii<0)?0:ii);

  }
}


Measured memory_bytes: 23764
N,M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

sortAB = sorted(AB)

ans = 0
num = M
for i in sortAB:
    a,b = i
    if num >= b:
        num -= b
        ans += a* b
    else:
        ans += a * num
        break

print(ans)

Measured memory_bytes: 28648
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

N = input()
if N[-1] == '3':
    print('bon')
elif N[-1] in '0168':
    print('pon')
else:
    print('hon')

    



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

#define MAXSIZE 100000

void reverse(char *);
int isMatched(const char *, const char *);

int main(){
  int i, j = 0, count = 0;
  int status = 1;
  char s[MAXSIZE];
  char test[4][8];
  strcpy(test[0], "dream");
  strcpy(test[1], "dreamer");
  strcpy(test[2], "erase");
  strcpy(test[3], "eraser");
  char temp;

  // get and reverse
  scanf("%s", s);
  reverse(s);
  for(i = 0; i < 4; i++){
    reverse(test[i]);
  }
  
  while(status){
    status = 0;
    for(i = 0; i < 4; i++){
       if(!strncmp(&s[count], test[i],strlen(test[i]))){
        count += strlen(test[i]);
        status = 1;
        break;
      }
    }
  }

  printf("%s\n", (count==strlen(s)) ? "YES": "NO" );
  

  return 0;
}

void
reverse(char *str){
  int i;
  char temp;
  for(i = 0; i < strlen(str)/2; i++){
    temp = str[i];
    str[i] = str[strlen(str) -1 -i];
    str[strlen(str) - 1 - i] = temp;
  }
}

Measured memory_bytes: 256
X, N = map(int, input().split())

if N == 0:
    print(X)
    exit()


P = list(map(int, input().split()))
A = []
for a in range(-1, 102):
    A.append(a)

for a in P:
    A.remove(a)

if X not in P:
    print(X)
    exit()
else:
    A.append(X)

A.sort()
C = A.index(X)
D = A[C+1]
E = A[C-1]

if D-X == X-E:
    print(E)
elif D-X > X-E:
    print(E)
else:
    print(D)

Measured memory_bytes: 9212
import itertools

n = int(input())
town_map = []
for i in range(n):
    town_map.append(list(map(int, input().split())))

town_name = []
for i in range(n):
    tmp_str_town_name = str(i)
    town_name.append(tmp_str_town_name)

p = list(itertools.permutations(town_name, n))

distance = 0
for i in range(len(p)):
    one_path = p[i]
    for j in range(n - 1):
        l = int(one_path[j])
        r = int(one_path[j + 1])
        lx, ly = town_map[l]
        rx, ry = town_map[r]
        distance += ((rx - lx)**2 + (ry - ly)**2) ** (1/2)

print(distance / len(p))

Measured memory_bytes: 13992
def d_binomial_coefficients():
    from bisect import bisect_left
    N = int(input())
    A = sorted([int(i) for i in input().split()])  # ソートしておく

    n = A[-1]  # comb(n, r) の n をこの値以外にする理由はない
    r = min(A[:-1], key=lambda x: abs(n / 2 - x))
    return '{0} {1}'.format(n, r)

print(d_binomial_coefficients())

Measured memory_bytes: 14052
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("filed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let a:f64 = read();
    let b:f64 = read();
    println!("{}", ((a+b)/2.0).ceil() as u64);
}


Measured memory_bytes: 2644
n = int(input())
tst = [[] for i in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        x,y = map(int,input().split())
        tst[i].append([x,y])
ans = 0
for bit in range(1<<n):
    honest = [0]*n
    check = 1
    for i in range(n):
        if (bit>>i)&1:
            honest[-1-i] = 1
    for i in range(n):
        if not honest[i]:
            continue
        for l in tst[i]:
            if l[1]!=honest[l[0]-1]:
                check = 0
                break
    if check:
        ans = max(ans,sum(honest))
print(ans)

Measured memory_bytes: 9236
/*
 * @Author: RBQRBQ
 * @Date: 2020-04-05 14:49:27
 * @LastEditors: RBQRBQ
 * @LastEditTime: 2020-04-05 15:20:46
 */
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef pair<int,int> pii;
namespace IO{
    template<typename T>inline void read(T &x){
        x=0;ll f=1;char ch=getchar();
        while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
        while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
        x=x*f;
    }
}
using namespace IO;
const int maxn = 500000+10;
char S[maxn];
int a[maxn];
int main()
{
    scanf("%s",S);
    int len=strlen(S);
    for(int i=0;i<len;i++)
    {
        if(S[i]=='<')
        a[i+1]=a[i]+1;
    }
    for(int i=len-1;i>=0;i--)
    {
        if(S[i]=='>')
        a[i]=max(a[i],a[i+1]+1);
    }
    ll sum=0;
    for(int i=0;i<=len;i++)
    sum+=a[i];
    cout<<sum;
}

Measured memory_bytes: 2688
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include<algorithm>
#include<string>
#include <map>
#include <queue>
#include <stack>
#include<set>
#include<math.h>

#define DIV 1000000007
using namespace std;
using ll = long long;

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

	map<string, int> mp;
	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		mp[s]++;
	}
	
	int cnt = 0;
	for (auto x : mp) {
		cnt++;
	}

	cout << cnt << endl;
}


Measured memory_bytes: 19204
#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;

int a[1000005];
int main()
{
  int k, n;
  cin >> k >> n;
  rep(i, n) cin >> a[i];
  int ans = 1e9 + 1;
  rep(i, n)
  {
    int cw, ccw;
    if (i)
      cw = k - (a[i] - a[i - 1]);
    else
      cw = k - (a[i] + k - a[n - 1]);
    if (i + 1 == n)
      ccw = k - (a[0] - a[i]);
    else
      ccw = k - (a[i + 1] - a[i]);
    int temp = min(cw, ccw);
    ans = min(ans, temp);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1024
// C - Cat Snuke and a Voyage
#include <bits/stdc++.h>
using namespace std;

bool calc(int n, int x, int y, vector<bool> &P){
	if(x != n) return false;
	if(P[y-1]) return true;
	P[y-1] = true;
	return false;
}

int main(){
	int N,M; cin>>N>>M;
	vector<bool> P(N);
	while(M--){
		int a,b; cin>>a>>b;
		if(calc(1, a, b, P) || calc(N, b, a, P)) break;
	}
	cout<< (M<0? "IMPOSSIBLE":"POSSIBLE") <<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll  long long
#define FASTINOUT ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
map<int,int>cnt;
int main()
{
    FASTINOUT;
    int x,n;
    cin>>x>>n;
    int y[n];
    for (int i=0;i<n;i++){
        cin>>y[i];
        cnt[y[i]]++;
    }
    int dif=1e9,ans=0;
    for (int i=-100;i<=200;i++){
        if (!cnt[i]){
            if (abs(x-i)<dif){
                ans=i;
                dif=x-i;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3652
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=5005;
const int mod=1e9+7;
int n,p[N],par[N],sz[N],cycle_cnt,val[N],gt[N],dp[N][N];
bool kt[N];

int Power(int x,int n)
{
    if(!n) return 1;
    if(n%2) return Power(x,n-1)*x%mod;
    int tmp=Power(x,n/2);
    return tmp*tmp%mod;
}

int Find(int x)
{
    if(x==par[x]) return x;
    return par[x]=Find(par[x]);
}

void Union(int a,int b)
{
    int u=Find(a);
    int v=Find(b);
    if(u==v)
    {
        cycle_cnt++;
        return ;
    }
    par[u]=v;
    sz[v]+=sz[u];
}

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    int k=0;
    gt[0]=1;
    for(int i=1;i<=n;i++)
    {
        sz[i]=1;
        par[i]=i;
        gt[i]=gt[i-1]*i%mod;
    }
    for(int i=1;i<=n;i++)
    {
        cin>>p[i];
        if(p[i]!=-1) Union(i,p[i]);
        else k++;
    }
    for(int i=1;i<=n;i++) if(p[i]==-1) kt[Find(i)]=true;
    int m=0;
    for(int i=1;i<=n;i++) if(i==Find(i)&&kt[i]) val[++m]=sz[i];
    int res=(n-cycle_cnt)*Power(n-1,k)%mod;
    dp[0][0]=1;
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<=i;j++)
        {
            dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod;
            dp[i+1][j+1]=(dp[i+1][j+1]+dp[i][j]*val[i+1]%mod)%mod;
        }
    }
    int sub=0;
    for(int i=1;i<=m;i++) sub=(sub+(val[i]-1)*Power(n-1,k-1)%mod)%mod;
    for(int i=2;i<=m;i++) sub=(sub+dp[m][i]*gt[i-1]%mod*Power(n-1,k-i)%mod)%mod;
    cout<<(res-sub+mod)%mod;
}


Measured memory_bytes: 120456
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <set>

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())

using namespace std;
typedef long long ll;

int main(int argc, const char * argv[]) {
//    ifstream in("input.txt");
//    cin.rdbuf(in.rdbuf());
    
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n;
    cin >> n;
    if (n == 1) cout << "Hello World" << endl;
    else
    {
        int a, b;
        cin >> a >> b;
        cout << a + b << endl;
    }
    
    
    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pint pair<int, int>
#define pll pair<ll, ll>
#define vint vector<int >
#define vll vector<ll >
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (ll i = (a); i < (b); ++i)
#define REP(i,n) for (int i = 0; i < (n); ++i)
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
int main(){
    ll x;
    cin >> x;
    FOR(a,0,1000){
        FOR(b,0,1000){
            if(a-b!=0 && x%(a-b)==0 && a*a*a*a*a-b*b*b*b*b == x){
                cout << a << " " << b << endl;
                return 0;
            }else if(a+b!=0 && x%(a+b)==0 && a*a*a*a*a+b*b*b*b*b == x){
                cout << a << " " << -b << endl;
                return 0;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int (i)=0;i<(n);i++)
#define REP(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define INF INT_MAX
#define MOD 1000000007
#define fcout cout << fixed << setprecision(15)
#define int long long
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)?"YES":"NO")
#define sec second
#define fir first
typedef long long ll;
typedef pair<int, int> P;
typedef priority_queue<int> pque;
typedef vector<int> Vec;
int gcd(int a,int b){return b?gcd(b,a%b):a;};
int lcm(int a,int b){return a/gcd(a,b)*b;};
int mod(int a,int b){return (a+b-1)/b;};
template<typename A, size_t N, typename T>
void Fill(A(&array)[N],const T &val){std::fill((T*)array,(T*)(array+N),val);}
template<class T>inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;};
template<class T>inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;};



signed main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    
    string k;
    int d;
    cin >> k >> d;
    vector<vector<int>> dp(d, vector<int>(2));
    dp[0][true] = 1;

    rep(i, k.size()) {
        int here = k[i] - '0';
        vector<vector<int>> after(d, vector<int>(2));

        for(int prevmod = 0; prevmod < d; prevmod++) {
            for(int now = 0; now < 10; now++) {
                int nowmod = (prevmod + now) % d;
                if(now < here) {
                    after[nowmod][false] += dp[prevmod][true];
                    after[nowmod][true] %= MOD;
                } else if(now == here) {
                    after[nowmod][true] += dp[prevmod][true];
                    after[nowmod][true] %= MOD;
                }
                after[nowmod][false] += dp[prevmod][false];
                after[nowmod][false] %= MOD;
            }
        }
        dp = after;
    }

    cout << (dp[0][true] + dp[0][false] - 1 + MOD) % MOD << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <numeric>
#include <algorithm>
#include <sstream>
#include <string>
#include <map>
#include <set>
using namespace std;

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


int64_t gcd(int64_t a, int64_t b) {
	if (a%b==0) return b;
	else return gcd(b, a%b);
}

int64_t lcm(int64_t a, int64_t b) {
	return a / gcd(a, b) * b;
}

int main() {
	int64_t a, b, c, d;
	cin >> a >> b >> c >> d;

	int64_t num_b = b/c + b/d - b/lcm(c, d);
	int64_t num_a = (a-1)/c + (a-1)/d - (a-1)/lcm(c, d);
	cout << b-a +1 - (num_b - num_a) << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;


public class Main 
{
	public static void main(String[] args)
	{
		Scanner scanner = new Scanner(System.in);
		
		for(; scanner.hasNext();)
		{
			String in = scanner.nextLine();
	
			int shift = getShift(in);
			
			String out = "";
			for(int i=0; i<in.length(); i++)
			{
				out += shiftWord(in.charAt(i), shift);
			}
			System.out.println(out);
		}
	}
	
	static int getShift(String str)
	{
		String[] word = str.split("[ .]");
		
		for(int i=0; i<word.length; i++)
		{
			for(int j=0; j<26; j++)
			{
				String w = "";
				for(int k=0; k<word[i].length(); k++)
				{
					w += shiftWord(word[i].charAt(k), j);
				}
				if(w.equals("the") || w.equals("this") || w.equals("that"))
				{
					return j;
				}
			}
		}
		return 0;
	}
	
	static String shiftWord(char c, int shift)
	{
		char w = c;
		if('a'<=c && c<='z')
		{
			w = (char)(c + shift);
			if(w > 'z')
			{
				w = (char)('a' + (w - 'z')  -1); 
			}
		}
		return String.valueOf(w);
	}
}

Measured memory_bytes: 25948
#include <algorithm>
#include <bitset>
#include <boost/dynamic_bitset.hpp>
#include <cfloat>
#include <cmath>
#include <ctime>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <typeindex>
#include <typeinfo>
#include <vector>

#define DEBUG(x) cout << #x << ": " << x << endl
#define INFILE() freopen("input.txt", "r", stdin)
#define REP(i, a, b) for (int i = a; i < b; i++)
#define ALL(s) begin(s), end(s)
#define RALL(s) rbegin(s), rend(s)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using i_i = pair<int, int>;
using ll_i = pair<ll, int>;
using i_ll = pair<int, ll>;
using d_i = pair<double, int>;
using ll_ll = pair<ll, ll>;
using d_d = pair<double, double>;

static constexpr ll LL_MOD = 1000000009;
static constexpr int I_MOD = 1000000007;
static constexpr double EPS = numeric_limits<double>::epsilon();
static constexpr double PI = 3.14159265358979323846264338327950288;

template <class T> static void scan(vector<T> &v);
static void scan(vector<string> &v, bool isWord = true);
static boost::dynamic_bitset<> scan(char trueValue = 'o');

int main(int argc, char *argv[]) {
	// INFILE();
  int k, s;
  cin >> k >> s;

  int count = 0;
  REP(i, 0, k + 1) {
    REP(j, 0, k + 1) {
      if ((s - i - j) < 0 || (s - i - j) > k) {
        continue;
      }
      count++;
    }
  }

  cout << count << "\n";
  return 0;
}

template <class T> static void scan(vector<T> &v) {
  map<type_index, const char *const> m = {{typeid(int), "%d"},
                                          {typeid(ll), "%lld"},
                                          {typeid(double), "%lf"},
                                          {typeid(char), "%c"}};

  auto tFormat = m[typeid(T)];

  for (T &n : v) {
    scanf(tFormat, &n);
  }
}

static void scan(vector<string> &v, bool isWord) {
  if (isWord) {
    for (auto &n : v) {
      cin >> n;
    }
    return;
  }

  int i = 0, size = v.size();
  string s;
  getline(cin, s);

  if (s.size() != 0) {
    i++;
    v[0] = s;
  }

  for (; i < size; ++i) {
    getline(cin, v[i]);
  }
}

static boost::dynamic_bitset<> scan(char trueValue) {
  string s;
  getline(cin, s);

  if (s.size() == 0) {
    getline(cin, s);
  }

  for_each(begin(s), end(s),
           [trueValue](char &c) { c = (c == trueValue) ? '1' : '0'; });
  return boost::dynamic_bitset<>(string(rbegin(s), rend(s)));
}


Measured memory_bytes: 256
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;
typedef long long ll;

int r;


int main(){
  cin >> r;
  cout << pow(r,2) << endl;
}


Measured memory_bytes: 888
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll a,b;
    cin>>a>>b;
    ll x=b-(a-1),y=b+(a-1);
    for(ll i=x;i<=y;i++)
    {
        cout<<i<<" ";
    }
    
    return 0;
}

Measured memory_bytes: 256
class Score:
	def __init__(self, id, solve, penalty):
		self.id = id
		self.solve = solve
		self.penalty = penalty

	def __lt__(self, other):
		if (self.penalty == other.penalty) and (self.solve == other.solve):
			return self.id < other.id
		elif (self.solve == other.solve):
			return self.penalty < other.penalty
		else:
			return self.solve > other.solve

while True:
	t, p, r = map(int, input().split())
	if (t, p, r) == (0, 0, 0):
		break
	tp = [[0]*p for i in range(t)]
	ts = [Score(i+1,0,0) for i in range(t)]
	for i in range(r):
		tid, pid, time, message = input().split()
		tid, pid, time = map(int, [tid, pid, time])
		if message == 'CORRECT':
			ts[tid-1].solve += 1
			ts[tid-1].penalty += (tp[tid-1][pid-1]*1200 + time)
		else:
			tp[tid-1][pid-1] += 1
	ts = sorted(ts)
	for s in ts:
		print('{} {} {}'.format(s.id, s.solve, s.penalty))

Measured memory_bytes: 7796
#include <bits/stdc++.h>
using namespace std;
typedef long long llong;

vector<int> E[100005];
int d_u[100005];
int d_v[100005];

void dfs_u(int V, int p){
	if(p!=-1)d_u[V]=d_u[p]+1;
	for(int u:E[V]){
		if(u==p) continue;
		dfs_u(u, V);
	}
}

void dfs_v(int V, int p){
	if(p!=-1)d_v[V]=d_v[p]+1;
	for(int u:E[V]){
		if(u==p) continue;
		dfs_v(u, V);
	}
}

int main(void) {
  int n, u, v;
  
  cin >> n >> u >> v; u--; v--;

  int a, b;
  for(int i=0;i<n-1;i++) {
    cin >> a >> b; a--; b--;
    E[a].push_back(b);
    E[b].push_back(a);
  }

  dfs_u(u, -1);
  dfs_v(v, -1);

  int ans=0;
  for(int i=0;i<n;i++) {
    if(d_u[i]<d_v[i]) ans = max(ans, d_v[i]);
  }
  
  cout << ans-1 << endl;

  return (0);
}


Measured memory_bytes: 10368
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;

struct UnionFind {
	vector<ll> a_parent;
	vector<ll> a_size;

	UnionFind(ll n)
		: a_parent(n, -1)
		, a_size(n, 1)
	{
		for (ll i = 0; i < n; ++i) {
			a_parent[i] = i;
		}
	}

	void Prll() {
		for (ll i = 0; i < (ll)a_parent.size(); ++i) {
			cout << i << "," << a_parent[i] << "," << a_size[i] << endl;
		}
	}

	ll Find(ll i) {
		ll p = a_parent[i];
		if (p == i) {
			return p;
		}
		return Find(p);
	}

	void Union(ll i, ll j) {
		ll ip = Find(i);
		ll jp = Find(j);
		if (ip != jp) {
			if (a_size[ip] >= a_size[jp]) {
				a_parent[jp] = ip;
				a_size[ip] += a_size[jp];
				a_size[jp] = 0;
			}
			else {
				a_parent[ip] = jp;
				a_size[jp] += a_size[ip];
				a_size[ip] = 0;
			}
		}
	}
};

int main()
{
	ll N, M;
	cin >> N >> M;
	vector<ll> A(M, 0);
	vector<ll> B(M, 0);
	for (ll i = 0; i < M; ++i) {
		cin >> A[i] >> B[i];
	}
	UnionFind uf(N+1);
	vector<ll> ans(M, 0);
	ans[M-1] = N * (N - 1) / 2;
	ll uu = ans[M - 1];
	for (ll i = M - 1; i >= 0; --i) {
		ans[i] = uu;
		//uf.Prll(); cout << endl;
		ll ra = uf.Find(A[i]);
		ll rb = uf.Find(B[i]);
		if (ra != rb) {
			//cout << "not connected " << A[i] << ":" << B[i] << endl;
			uu -= uf.a_size[ra] * uf.a_size[rb];
		}
		uf.Union(A[i], B[i]);
	}
	for (ll i = 0; i < M; ++i) {
		cout << ans[i] << endl;
	}
	return 0;
}



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

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<bool> VB;
typedef vector<double> VD;
typedef vector<string> VS;
typedef vector<char> VC;
typedef vector<VC> VVC;
typedef pair<int, int> PII;
typedef long long LL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef pair<LL,LL> PLL;
typedef vector<PII> VPII;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SQ(a) ((a)*(a))
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define LB lower_bound
#define UB upper_bound

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

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL INF = 1e9;
const LL MOD = 1e9+7;

//other
//-------------------------------------------
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define FI first
#define SE second

//memo
// setprecision()

LL Gcd(LL a, LL b) {
  return __gcd(a,b);
}

LL Lcm(LL a, LL b) {
  LL abd = Gcd(a,b);
  LL x = a / abd, y = b / abd;
  
  return x*y*abd;
}


LL RepSqu(LL N, LL P, LL M) {
  if(P == 0) {
    return 1;
  }
  if(P%2 == 0) {
    LL t = RepSqu(N, P/2, M);
    return t*t % M;
  }
  return (N * RepSqu(N, P-1, M)) % M;
}

bool IsPrime(LL N){
  if(N >= 1) return false;
  for(int i = 2; i*i <= N; ++i){
    if(N%i == 0) return false;
  }
  return true;
}

bool ComPaiSec(PII a, PII b){
  if(a.SE != b.SE){
    return a.SE < b.SE;
  }else{
    return a.FI < b.FI;
  }
}

int main() {
  
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int N;
  cin >> N;
  LL ans = 0;
  VLL A(N), L(N),R(N);
  REP(i,N){
    cin >> A.at(i);
  }
  
  L.at(1) = A.at(0);
  R.at(N-2) = A.at(N-1);
  
  FOR(i,1,N-1){
    L.at(i+1) = Gcd(L.at(i),A.at(i));
  }
  
  for(int i = N-3; i>=0; --i){
    R.at(i) = Gcd(R.at(i+1),A.at(i+1));
  }
  
  REP(i,N){
    LL a = Gcd(L.at(i),R.at(i));
    chmax(ans,a);
  }
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
#define exrep(i, a, b) for(long long i = a; i <= b; i++)
#define rep(i,n)for(long long i=0;i<(n);i++)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
const ll MOD=1e9+7;
const ll INF=1e18;
const int MAX=510000;
const double pi=acos(-1);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

ll gcd(ll x, ll y){
  if(x%y==0)return y;
  return gcd(y,x%y);
}
ll lcm(ll x,ll y){
  return x/gcd(x,y)*y;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);  
  
  string s;
  cin >> s;
  int n=s.size();
  rep(i,n/2){
    string t=s.substr(0,s.size()/2);
    string u=s.substr(s.size()/2);
    if(u==t && i>0){
      cout << u.size()*2 << endl;
      return 0;
    }
    else s=s.substr(0,s.size()-2);
  }
}


Measured memory_bytes: 256
#include <functional>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <iomanip>
#include <utility>
#include <cstdlib>
#include <sstream>
#include <bitset>
#include <vector>
#include <cstdio>
#include <ctime>
#include <queue>
#include <deque>
#include <cmath>
#include <stack>
#include <list>
#include <map>
#include <set>

using namespace std;

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

#define dump(x)  cerr << #x << " = " << (x) << endl
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back

bool isLeep(int n){
    if((n%4==0 && n%100!=0) || n%400==0){
        return true;
    }
    else return false;
}


int main() {
    int a[5]={};
    char ch;
    while(cin>>a[0]>>ch>>a[1]>>ch>>a[2]>>ch>>a[3]>>ch>>a[4]){
        sort(a,a+5);
        if( (a[0]==a[1] && a[1]==a[2] && a[2]==a[3]) || (a[1]==a[2] && a[2]==a[3] && a[3]==a[4]) )cout<<"four card"<<endl;
        else if( (a[0]==a[1] && a[1]==a[2] && a[3]==a[4]) || (a[0]==a[1] && a[2]==a[3] && a[3]==a[4]) )cout<<"full house"<<endl;
        else if( (a[0]+1==a[1] && a[1]+1==a[2] && a[2]+1==a[3] && a[3]+1==a[4]) || (a[0]==1 && a[1]==10 && a[2]==11 && a[3]==12 && a[4]==13) )cout<<"straight"<<endl;
        else if( (a[0]==a[1] && a[1]==a[2]) || (a[1]==a[2] && a[2]==a[3]) || (a[2]==a[3] && a[3]==a[4]) )cout<<"three card"<<endl;
        else if( (a[0]==a[1] && (a[2]==a[3] || a[3]==a[4] )) || (a[1]==a[2] && a[3]==a[4]) )cout<<"two pair"<<endl;
        else if( a[0]==a[1] || a[1]==a[2] || a[2]==a[3] || a[3]==a[4] )cout<<"one pair"<<endl;
        else cout<<"null"<<endl;
    }
    
    return 0;
}

Measured memory_bytes: 1176
#include<bits/stdc++.h>
using namespace std;
typedef long long signed int ll;

int main(){
    int n;
    int l[1000];
    cin>>n;
    for(int i=0;i<n;i++) cin>>l[i];
    sort(l,l+n);
    int a=l[n-1];
    int b=0;
    for(int i=0;i<n-1;i++){
        b+=l[i];
    }
    if(a<b) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}


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

int n, s;
int COUNT = 0;
int A[10];

void dfs(int cur, int sum){
    if(cur == n){
        if(sum == s){
            COUNT++;
        }
    }
    else{
        if(cur == 0) {
            for(int i = 0; i < 10; i++){
                A[cur] = i;
                dfs(cur+1, sum+i);
            }
        }
        else {
            for(int i = A[cur-1] + 1; i < 10; i++){
                A[cur] = i;
                dfs(cur+1, sum+i);
            }
        }
    }
}

int main(void){
    while(cin >> n >> s){
        if(n == 0 && s == 0)
            break;
        COUNT = 0;
        dfs(0, 0);
        cout << COUNT << endl;
    }
}



Measured memory_bytes: 3016
import java.util.Scanner;

class Main {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int D = scanner.nextInt();
    int N = scanner.nextInt();

    if (N == 100) N += 1;
    int i = 1;
    while (D > 0) {
      i *= 100;
      D--;
    }
    System.out.println(i * N);
  }
}


Measured memory_bytes: 21716
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <climits>
using namespace std;

#define ALL(v) begin(v),end(v)
typedef pair<int,int> pii;

int main(){
	int n;
	scanf("%d", &n);
	vector<pii> vals(n);
	for(int i = 0; i < n; ++i){
		scanf("%d%d", &vals[i].second, &vals[i].first);
	}
	int thr = min(n, 5000);
	vector<vector<pii>> rs(thr);
	rs[0].emplace_back(0, 0);
	rs[0].emplace_back(vals[0]);

	vector<pii> tmp;
	for(int u = 1; u < thr; ++u){
		int par = (u - 1) >> 1;
		tmp.clear();
		for(const pii &p : rs[par]){
			tmp.emplace_back(p.first + vals[u].first, p.second + vals[u].second);
		}
		merge(ALL(rs[par]), ALL(tmp), back_inserter(rs[u]));
	}
	for(int u = 0; u < thr; ++u){
		int prv = 0;
		for(pii &p : rs[u]){
			p.second = prv = max(p.second, prv);
		}
	}

	int q;
	scanf("%d", &q);
	for(; q--; ){
		int v, l;
		scanf("%d%d", &v, &l);
		--v;
		
		int ans = 0;
		if(v < thr){
			ans = upper_bound(ALL(rs[v]), pii(l, INT_MAX))[-1].second;
		}
		else{
			tmp.clear();
			while(v >= thr){
				tmp.push_back(vals[v]);
				v = (v - 1) >> 1;
			}

			const vector<pii> &r = rs[v];
			int sz = tmp.size();
			for(int S = 1 << sz; S--; ){
				int x = 0, y = 0;
				for(int i = 0; i < sz; ++i){
					if(S >> i & 1){
						x += tmp[i].first;
						y += tmp[i].second;
					}
				}
				if(x > l){ continue; }
				int z = upper_bound(ALL(r), pii(l - x, INT_MAX))[-1].second;
				ans = max(ans, y + z);
			}
		}
		printf("%d\n", ans);
	}
}


Measured memory_bytes: 150324
import java.util.Scanner;
public class Main{
	public static void main(String[] args) {
		Scanner sc =new Scanner(System.in);
		int a =sc.nextInt();
		int b =sc.nextInt();
		int c =sc.nextInt();
		int d=a+b+c;
		if(d>=22) {
			System.out.print("bust");
		}else {
			System.out.print("win");
		}
		sc.close();
	}
}


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

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

	long long a = 0, b = 0;
	for( int i = 1; i <= n; i++ ) {
		if( ( i % k ) == 0 ) {
			a++;
		}
		if( ( i % k ) == k / 2 ) {
			b++;
		}
	}
	long long ans = a * a * a;
	if( (k % 2) == 0 ) {
		ans += b * b * b;
	}

	cout << ans << endl;

	return 0;
}


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

int main() {

int N;
cin >> N;

vector<int> X(N);
for (int i = 0; i < N; i++) {
  cin >> X.at(i);
}  

int sum = 0 , sum_min = 0, power = 0;
int p = 0;
int end = 0;

for (int i = 0; i < N; i++) {
  end = max( end, X.at(i));
}   
  
for (int j = 0; j <= end; j++) {
  p = j;

  for (int i = 0; i < N; i++) {
  power = ( X.at(i) - p )*( X.at(i) - p );
  sum += power;
    //cout << power << endl;
  }
  
  if ( j == 0 ) sum_min = sum;
  else {
  sum_min = min (sum, sum_min);
   // cout << sum << endl;
  }
    //cout << sum << " " << sum_min<< endl;  
	sum = 0;
}  
  
  // 出力
    cout << sum_min << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void){
    int a,b;
    scanf("%d %d",&a,&b);
    int d=a/b;
    int r=a%b;
    double f=(double)a/b;
    printf("%d %d %7.5f\n",d,r,f);
    return 0;
}


Measured memory_bytes: 2100
#include<bits/stdc++.h>
const int M=300000;//M=1e6+100;
typedef long long int ll;
using namespace std;


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	string s;
	cin>>s;
	for(int i=0;i<s.size();i++)
	{
		cout<<'x';
	}
}

Measured memory_bytes: 3652
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

H, W, K = MAP()
grid = [[]] * H
for i in range(H):
    grid[i] = list(input())

ans = 0
for bit1 in range(1<<H):
    for bit2 in range(1<<W):
        cnt = 0
        for i in range(H):
            for j in range(W):
                if grid[i][j] == '#' and (not bit1>>i & 1) and (not bit2>>j & 1):
                    cnt += 1
        if cnt == K:
            ans += 1
print(ans)


Measured memory_bytes: 9556
#include <stdio.h>

int main(void)
{
	int a,b,c;
	c=1;
	scanf("%d %d",&a,&b);
	if(a>8){
		c=c-1;
	}
	if(b>8){
		c=c-1;
	}
	if(c>0){
		printf("Yay!");
	}else{
		printf(":(");
	}
	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
    string a;
    cin>>a;
    int l,r;
    for(int i=0;i<a.size();i++)
    {
        if(a[i]=='A')  //从左向右找
        {
            l=i;
            break;
        }       
    } 
    for(int i=a.size()-1;i>=0;i--)
    {
        if(a[i]=='Z')  //从右向左找
        {
            r=i;
            break;
        }
    }
    cout<<r-l+1<<endl;  //加上端头的1
    return 0;
}

Measured memory_bytes: 640
n = int(input())
mn = 1e10

for i in range(n+1):
    ans = 0
    a, b = i, n-i

    while a>=6:
        a, mo = divmod(a, 6)
        ans += mo
    ans += a

    while b>=9:
        b, mo = divmod(b, 9)
        ans += mo
    ans += b

    mn = min(mn, ans)
print(mn)

Measured memory_bytes: 3064
#include<stdio.h>
#define MAX 44
int F[MAX]={0};

int fibonacci(int n){
  if(n==0 || n==1)return F[n]=1;
  
  if(F[n]!=0)return F[n];

  return F[n]=fibonacci(n-2)+fibonacci(n-1);
}


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

  res=fibonacci(n);
  
  printf("%d\n",res);
  return 0;
}



Measured memory_bytes: 2056
#include <bits/stdc++.h>
#define REP(i, a, n) for(ll i=a; i<n; i++)
#define RREP(i, a, n) for(ll i=n-1; i>=a; i--)
typedef long long ll;
const ll mod =1e9+7;
const ll inf =1e18;
using namespace std;

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

    bool calc=false;
    REP(i, 1, 10){
        REP(j, 1, 10){
            if(i*j==n){
                calc=true;
            }
        }
    }

    if(calc) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256