akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(0), cin.tie(0) 
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const int inf = ~0u >> 1;
int main() {
    IO;
    int k, a, b;
    cin >> k >> a >> b;
    bool flag = false;
    for (int i = a; i <= b; ++i) {
        if (i % k == 0) {
            flag = true;
            break;
        }
    }
    cout << (flag ? "OK" : "NG") << endl;
    return 0;
}

Measured memory_bytes: 3592
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

typedef pair <int, int> pii;

const int MAXN = 200005;
const int offset = 1 << 18;
const int MOD = 1000000007;

int N, X, Y;
pii ball[MAXN];
vector <pii> t[2 * offset], v[2 * offset];
vector <int> comp[MAXN];
int dad[MAXN], rnk[MAXN];
int fact[MAXN], inv[MAXN];
int cnt[MAXN];
int sum[MAXN];

void load() {
	scanf("%d%d%d", &N, &X, &Y);
	for (int i = 0; i < N; i++)
		scanf("%d%d", &ball[i].second, &ball[i].first);
}

inline int mul(int x, int y) {
	return (long long)x * y % MOD;
}

int pot(int x, int y) {
	int res = 1;
	for (; y; y /= 2) {
		if (y % 2)
			res = mul(res, x);
		x = mul(x, x);
	}
	return res;
}

void add(int pos) {
	for (int x = pos + offset; x; x /= 2)
		t[x].push_back({ball[pos].second, pos});
}

void update(int x, int lo, int hi, int from, int to, int val, int type) {
	if (lo >= to || hi <= from)
		return;
	if (lo >= from && hi <= to) {
		v[x].push_back({val, type});
		return;
	}
	int mid = (lo + hi) / 2;
	update(2 * x, lo, mid, from, to, val, type);
	update(2 * x + 1, mid, hi, from, to, val, type);
}

void update(int from, int to, int val, int type) {
	update(1, 0, offset, from, to, val, type);
}

int find(int x) {
	return dad[x] == x ? x : dad[x] = find(dad[x]);
}

void join(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y)
		return;
	if (rnk[x] > rnk[y])
		swap(x, y);
	dad[x] = y;
	rnk[y] += rnk[x] == rnk[y];
}

int get_pos(int x, int val) {
	return lower_bound(t[x].begin(), t[x].end(), pii(val, -1)) - t[x].begin();
}

void merge(int x, int val, int lo, int hi) {
	if (lo >= hi)
		return;
	join(val, t[x][lo].second);
	sum[lo]++;
	sum[hi - 1]--;
}

void work(int x) {
	for (int i = 0; i < t[x].size(); i++)
		sum[i] = 0;
		
	sort(t[x].begin(), t[x].end());
	
	for (auto it : v[x]) {
		int lo = get_pos(x, ball[it.first].second);
		int hi = get_pos(x, ball[it.first].second + 1);
		if (it.second == 1) 
			merge(x, it.first, lo, hi);
		else {
			merge(x, it.first, 0, lo);
			merge(x, it.first, hi, t[x].size());
		}
	}
	
	for (int i = 0; i < (int)t[x].size() - 1; i++) {
		if (i)
			sum[i] += sum[i - 1];
		if (sum[i])
			join(t[x][i].second, t[x][i + 1].second);
	}
}

int get_last(int val) {
	return lower_bound(ball, ball + N, pii(val + 1, 0)) - ball;
}

int solve() {
	sort(ball, ball + N);
	
	for (int i = 0; i < N; i++) {
		dad[i] = i;
		update(i + 1, get_last(X - ball[i].first), i, 1);
		update(i + 1, get_last(Y - ball[i].first), i, 2);
		add(i);
	}
	
	for (int i = 0; i < 2 * offset; i++)
		work(i);
	
	for (int i = 0; i < N; i++)
		comp[find(i)].push_back(i);
	
	fact[0] = 1;
	for (int i = 1; i <= N; i++) {
		fact[i] = mul(fact[i - 1], i);
		inv[i] = pot(i, MOD - 2);
	}
	
	int sol = 1;
	for (int i = 0; i < N; i++) {
		sol = mul(sol, fact[comp[i].size()]);
		for (auto it : comp[i])
			sol = mul(sol, inv[++cnt[ball[it].second]]);
		for (auto it : comp[i])
			cnt[ball[it].second]--;
	}
	
	return sol;
}

int main() {
	load();
	printf("%d\n", solve());
	return 0;
}

Measured memory_bytes: 126428
import copy

N = int(input())

A = []

for i in range(N):
    A.append(int(input()))

max_A = max(A)

B = copy.deepcopy(A)

B.remove(max_A)

second_A = max(B)

for i in range(N):
    if A[i] == max_A:
        print(second_A)
    else:
        print(max_A)


Measured memory_bytes: 14568
/*
ID: i_love_7
TASK: 
LANG: C++
*/
//Written by Zhu Zeqi
//Come on,baby
//Hack,please
#include<cmath>
#include<math.h>
#include<ctype.h>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cwchar>
#include<cwctype>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#define CLR(x) memset(x,0,sizeof x)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define pii pair<int,int>
#define vi vector<int>
#define MAX 1000000000000000000
#define MOD 1000000007
#define PI 3.141592653589793238462
#define INF 0x3f3f3f3f
typedef long long ll;
//orz yht
using namespace std;
string i_s(int x){
	if(x==0)
	return "0";
	string ret="";
	while(x){
		ret=ret+(char)(x%10+'0');
		x/=10;
	}
	reverse(ret.begin(),ret.end());
	return ret;
}
string add(string a,string b){
	if(a=="")
	a="0";
	if(b=="")
	b="0";
	if(a.length()<b.length())
	swap(a,b);
	while(b.length()<a.length()){
		b='0'+b;
	}
	for(int i=0;i<a.length();i++){
		a[i]=a[i]+(b[i]-'0');
	}
	bool big=false;
	for(int i=a.length()-1;i>=0;i--){
		if(big){
			a[i]++;
		}
		big=false;
		if(a[i]>'9'){
			a[i]=a[i]-10;
			big=true;
		}
	}
	if(big)
	a='1'+a;
	return a;
}
string mul(string a,string b){
	vector<int> va,vb;
	if(a=="0" || b=="0")
	return "0";
	string ans;
	for(int i=0;i<a.length();i++){
		va.push_back(a[i]-'0');
	}
	for(int i=0;i<b.length();i++){
		vb.push_back(b[i]-'0');
	}
	reverse(va.begin(),va.end());
	reverse(vb.begin(),vb.end());
	vector<int> res;
	res.clear();
	res.resize(1005);
	for(int i=0;i<a.length();i++){
		for(int j=0;j<b.length();j++){
			res[i+j]+=(va[i]*vb[j]);
		}
	}
	for(int i=0;i<1005;i++){
		if(res[i]>9){
			res[i+1]+=(res[i]/10);
			res[i]%=10;
		}
	}
	for(int i=0;i<1005;i++){
		ans+=(res[i]+'0');
	}
	reverse(ans.begin(),ans.end());
	int k=0;
	while(ans[k]=='0'){
		k++;
	}
	ans=ans.substr(k);
	return ans;
}
bool is_prime(int n){
	if(n<2)
    return false;
    for(int i=2;i*i<=n;i++)
    if(n%i==0)
    return false;
    return true;
}
ll a,b,k;
int main(){
	//freopen("input.in","r",stdin);
	//freopen("output.out","w",stdout);
	cin>>a>>b>>k;
	ll i;
	for(i=a;i<=b;i++)
	if(i-a+1<=k)
	cout<<i<<endl;
	else
	break;
	for(ll j=max(i,b-k+1);j<=b;j++){
		cout<<j<<endl;
	}
	//system("pause");
	return 0;
}


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

int main() {
  string s, t; cin >> s >> t;
  if (s.size() != t.size()) {cout << "No" << endl; return 0;}
  ll N = s.size();
  set<ll> cs1[26], cs2[26];
  for (ll i = 0; i < N; i++) {
    ll x = s[i] - 'a';
    ll y = t[i] - 'a';
    cs1[x].insert(y); cs2[y].insert(x);
  }
  bool ok = true;
  for (ll i = 0; i < 26; i++) {
    if (cs1[i].size() > 1 || cs2[i].size() > 1) ok = false;
  }
  if (ok) {cout << "Yes" << endl;}
  else {cout << "No" << endl;}
}

Measured memory_bytes: 776
n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = input()

ans = 0
win = [True for _ in range(n)]
for i in range(n):
    
    if i-k >= 0 and t[i-k] == t[i] and win[i-k] == True:
        win[i] = False
    else:
        if t[i] == 'r':
            ans += p
        elif t[i] == 's':
            ans += r
        else:
            ans += s

print(ans)

Measured memory_bytes: 4212
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int main(){
    cin.tie(NULL); cout.tie(NULL);
    ios_base:: sync_with_stdio(false);
    ll a,b;cin>>a>>b;
    for(ll i=1;i<=(1e5);i++){
        ll v1 = (8*i)/100;
        ll v2 = (10*i)/100;

        if(v1==a && v2==b)return cout<<i , 0;
    }
    cout<<"-1";
}






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

typedef long long ll;
using namespace std;
using namespace atcoder;

#define _overload(_1, _2, _3, name, ...) name
#define _rep(i, n) for(ll i = 0; i < (ll)n; i++)
#define _repi(i, s, n) for(ll i = (ll)(s); i < (ll)n; i++)
#define REP(...) _overload(__VA_ARGS__, _repi, _rep,)(__VA_ARGS__)
#define all(v) (v).begin(),(v).end()
#define UNIQUE(v) (v).erase( unique( all(v) ), (v).end() );
#define MOD 1000000007

int main(){
	ll t;	cin >> t;
	ll n, m, a, b;

	REP(i, t){
		cin >> n >> m >> a >> b;
		cout << floor_sum(n, m, a, b) << endl;
	}

	return 0;
}


Measured memory_bytes: 3636
// -*- coding:utf-8-unix -*-

use proconio::input;

fn main() {
    input! {
        n: usize,
        s: String,
    }

    let vc: Vec<char> = s.chars().collect();
    let mut vidx = vec![vec![]; 3];
    for i in 0..n {
        match vc[i] {
            'R' => vidx[0].push(i as u32),
            'G' => vidx[1].push(i as u32),
            'B' => vidx[2].push(i as u32),
            _ => unreachable!(),
        }
    }

    let mut ans = vidx[0].len() * vidx[1].len() * vidx[2].len();
    for i in 0..n {
        for j in i + 1..n {
            if vc[i] == vc[j] {
                continue;
            }

            let k = 2 * j - i;
            if k >= n || vc[k] == vc[i] || vc[k] == vc[j] {
                continue;
            }

            ans -= 1;
        }
    }

    println!("{}", ans);
}


Measured memory_bytes: 2200
#include<bits/stdc++.h>
#define lson (o<<1)
#define rson (o<<1|1)
#define fi first
#define sc second
#define dbg(x) cout<<#x<<" = "<<(x)<<endl;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
using namespace std;
const double pi=acos(-1);
const double eps=1e-6;
inline int lowbit(int x)
{
	return x&(-x);
}
inline int read()
{
	int f=1,x=0;
	char ch;
	do
	{
		ch=getchar();
		if(ch=='-')f=-1;
	}
	while(ch<'0'||ch>'9');
	do
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	while(ch>='0'&&ch<='9');
	return f*x;
}
template<typename T> inline T max(T x,T y,T z)
{
	return max(max(x,y),z);
}
template<typename T> inline T min(T x,T y,T z)
{
	return min(min(x,y),z);
}
template<typename T> inline T sqr(T x)
{
	return x*x;
}
template<typename T> inline void checkmax(T &x,T y)
{
	x=max(x,y);
}
template<typename T> inline void checkmin(T &x,T y)
{
	x=min(x,y);
}
template<typename T> inline void read(T &x)
{
	x=0;
	T f=1;
	char ch;
	do
	{
		ch=getchar();
		if(ch=='-')f=-1;
	}
	while(ch<'0'||ch>'9');
	do x=x*10+ch-'0',ch=getchar();
	while(ch<='9'&&ch>='0');
	x*=f;
}
template<typename A,typename B,typename C> inline A fpow(A x,B p,C yql)
{
	A ans=1;
	for(; p; p>>=1,x=1LL*x*x%yql)if(p&1)ans=1LL*x*ans%yql;
	return ans;
}
struct FastIO
{
	static const int S=1310720;
	int wpos;
	char wbuf[S];
	FastIO():wpos(0) {}
	inline int xchar()
	{
		static char buf[S];
		static int len=0,pos=0;
		if(pos==len)pos=0,len=fread(buf,1,S,stdin);
		if(pos==len)return -1;
		return buf[pos++];
	}
	inline int read()
	{
		int c=xchar(),x=0;
		while(c<=32&&~c)c=xchar();
		if(c==-1)return -1;
		for(; '0'<=c&&c<='9'; c=xchar())x=x*10+c-'0';
		return x;
	}
} io;

int x,t;

int main()
{
	x=read();
	t=read();
	if(x>t)
	{
		printf("%d\n",x-t);
		return 0;
	}
	else
	{
		puts("0");
		return 0;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
typedef long long ll;
using namespace std;
const  ll INF = 1e9;
const  ll MOD = 1e9 + 7;
#define repi(i,n,init) for(ll i=init;i<(n);i++)

int main()
{
    char c;
    cin >> c;
    if(c == 'a'||c=='i'||c=='u'||c=='e'||c=='o'){
        puts("vowel");
    }else{
        puts("consonant");
    }
    return 0;
}

Measured memory_bytes: 256
import sys
# sys.stdin = open('input.txt')

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

MOD = 10**9 + 7
a = [i for i in range(n+1)]

ans = 0
for i in range(k, n+2):
    first = i * (a[0] + a[i-1]) / 2
    last = i * (a[-i] + a[-1]) / 2
    ans += last - first + 1
print(int(ans%MOD))

Measured memory_bytes: 16904
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int a = Integer.parseInt(sc.next());
        int b = Integer.parseInt(sc.next());
        int coin = 0;
        for (int i = 0; i < 2; i++) {
            if (a > b) {
                coin += a;
                a--;
            } else {
                coin += b;
                b--;
            }
        }
        
        System.out.println(coin);
    }
}


Measured memory_bytes: 22996
#include<bits/stdc++.h>
#define fast ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl "\n";
using namespace std;
typedef long long int ll;
bool possible(int mid,vector<int>a,int k)
{
    for(auto i:a)
    {
        k-=(i+mid-1)/mid -1;
    }
    if(k>=0)return true;
    return false;
}
int main()
{
    int n,k;
    cin>>n>>k;
    vector<int>a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    int mn =1,mx=(int)1e9+100;
    while(mn!=mx)
    {
        int mid = (mn)+(mx-mn)/2;
        if(possible(mid,a,k))
            mx = mid;
        else
            mn = mid+1;
    }
    cout<<mx<<endl;
    return 0;
}

Measured memory_bytes: 4832
#include <stdio.h>

int main(void)
{
  int n, b = 100000, sum = 0;
  scanf("%d", &n);
  
  for (int i = 0; i < n; i++) {
    int c;
    scanf("%d", &c);
    sum += (b < c ? b : c);
    b = c;
  } 
  
  printf("%d", sum);
  
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
#define int long long
using P = pair<int,int>;
signed main(){
    int n;cin >>n;
    int ans = 0;
    rep(i,n){
        int a;cin >> a;
        int cnt = 0;
        while(1){
            if(a%2 == 1)break;
            cnt++;
            a/=2;
        }
        ans += cnt;
    }
    cout <<ans << endl;
    
    return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
'''
所要時間は、分位であった。
'''


# ライブラリのインポート
#import re #正規表現
import sys
#import heapq
#import bisect
#import collections
#import math

def main():
    n, q = map(int, input().split())
    P = [i for i in range(n)]
    for line in sys.stdin:
        order = line.strip("\n").split()
        x,y = map(int, order[1:])
        if x > y: x, y = y, x
        while(1):
            x = P[x]
            if x == P[x]: break
        while(1):
            y = P[y]
            if y == P[y]: break
        if order[0] == "0": #unite
            P[x] = P[y] 
        elif order[0] == "1": #same
            print(1) if y == x else print(0)
    


    
if __name__ == '__main__':
    main()



Measured memory_bytes: 6672
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A, B, C;
  string answer;
  cin >> A >> B >> C;
  
  if (A == B){
    if ( B != C){
      cout << "Yes" << endl;
    }
    
    else {
      cout << "No" << endl;
    }
    
  }
  
  else if (B == C) {
    cout << "Yes" << endl;
  }
  
  else if (A == C){
    cout << "Yes" << endl;
  }
  
  else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    INF = float('inf')
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,x = LI()
    a = LI()

#    N0 = 2**(N.bit_length())
#    st = [INF] * (2*N0)

    def update(i,x):
        i += N0-1
        st[i] = x
        while i > 0:
            i = (i-1) // 2
            st[i] = min(st[i*2+1],st[i*2+2])

    def query(l,r):
        l += N0; r += N0
        ret = INF
        while l < r:
            if l % 2:
                ret = min(ret,st[l-1])
                l += 1
            if r % 2:
                r -= 1
                ret = min(ret,st[r-1])
            l >>= 1; r >>= 1
        return ret

#    for i,j in enumerate(a):
#        update(i,j)
    min_a = copy.copy(a)

    ans = INF
    for i in range(N):
        tmp = i * x
        for j in range(N):
            l = j - i
            min_a[j] = min(min_a[j],a[l])
            tmp += min_a[j]
        ans = min(ans,tmp)
    print(ans)




if __name__ == '__main__':
    main()

Measured memory_bytes: 75460
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for (int i = 0; i < n; ++i)
#define REP(i,k,n) for (int i = k; i <= n; ++i)
#define REPR(i,k,n) for (int i = k; i >= n; --i)
#define pb push_back
#define F first
#define S second
#define I insert
#define mp make_pair
#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()
#define debug1(a) cout<<" "<<#a<<" : "<<a<<"\n"
#define debug2(a,b) cout<<" "<<#a<<" : "<<a<<" "<<#b<<" : "<<b<<"\n"
#define debug3(a,b,c) cout<<" "<<#a<<" : "<<a<<" "<<#b<<" : "<<b<<" "<<#c<<" : "<<c<<"\n"
#define debug4(a,b,c,d) cout<<" "<<#a<<" : "<<a<<" "<<#b<<" : "<<b<<" "<<#c<<" : "<<c<<" "<<#d<<" : "<<d<<"\n"
// #define M 421412341324321
#define MOD 1000000007


signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	
	int n,k;
	cin>>n>>k;
	int a[n];
	rep(i,n)
	{
		cin>>a[i];
	}
	int y[n], x[n];
	rep(i,n)
	{
		int c=0;
		REP(j,0,n-1)
		{
			if (a[j]<a[i]) c++;
		}
		y[i]=c;
		// debug2(a[i],y[int]);
	}
	rep(i,n)
	{
		int c=0;
		REP(j,i+1,n-1)
		{
			if (a[i]>a[j]) c++;
		}
		x[i]=c;
		// debug2(a[i],c);
	}
	int ans=0;
	rep(i,n)
	{
		ans= ans+(k*x[i])%MOD  + ((((k*(k-1))/2)%MOD)*y[i])%MOD;
		ans%=MOD;
		// debug1(ans);
	}
	cout<<ans;
	

 
	
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
typedef long long ll;
#define rep(i, n) for (int (i) = 0; i < (n);++i)
using namespace std;

int main(){
    ll N,K;
    ll ans;
    cin >> N >> K;
    ans = K;
    for(int i=1;i<N;i++){
        ans *= K-1;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mp make_pair
#define X first
#define Y second 
using namespace std;
typedef pair<int,int> PII; 
typedef long long ll;
const int P = 1e9+7;
const int N = 200010;
char s[2][N];
int sum[2][N],len[2];
int main(){
	scanf("%s",s[0]);
	len[0] = strlen(s[0]);
	scanf("%s",s[1]);
	len[1] = strlen(s[1]);
	for(int i=1;i<=len[0];i++){
		sum[0][i]=sum[0][i-1]+(s[0][i-1]=='A'?1:2);
	}
	for(int i=1;i<=len[1];i++){
		sum[1][i]=sum[1][i-1]+(s[1][i-1]=='A'?1:2);
	}
	int Q;
	scanf("%d",&Q);
	while(Q--){
		int l1,r1,l2,r2;
		scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
		int a1 = (sum[0][r1]-sum[0][l1-1])%3;
		int a2 = (sum[1][r2]-sum[1][l2-1])%3;
		if(a1==a2) puts("YES"); else puts("NO");
	}
	return 0;
}

Measured memory_bytes: 1664
#include<algorithm>
#include<complex>
#include<ctype.h>
#include<iomanip>
#include<iostream>
#include<map>
#include<math.h>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<stdio.h>
#include<string>
#include<string>
#include<vector>

using namespace std;
typedef long long ll;

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("YES")
#define p_no() p("NO")

template < typename T >
void vprint(T &V){
	for(auto v : V){
    	cout << v << " ";
	}
	cout << endl;
}

const ll mod = 1e9 + 7;
const ll inf = 1e18;

struct Operation{
    int i0;
    int j0;
    int i1;
    int j1;
    
    Operation(int a, int b, int c, int d){
        i0 = a;
        j0 = b;
        i1 = c;
        j1 = d;
    }
};

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

    // input
    ll H, W;
    cin >> H >> W;

    vector<vector<ll> > A(H);
    FOR(i, 0, H){
        FOR(j, 0, W){
            ll a;
            cin >> a;
            A[i].push_back(a);
        }
    }

    vector<Operation> OP;

    FOR(i, 0, H){
        FOR(j, 0, W-1){
            if(A[i][j]%2==1){
                A[i][j]--;
                A[i][j+1]++;
                OP.push_back(Operation(i, j, i, j+1));
            }
        }
    }
    FOR(i, 0, H-1){
        if(A[i][W-1]%2==1){
            A[i][W-1]--;
            A[i+1][W-1]++;
            OP.push_back(Operation(i, W-1, i+1, W-1));
        }
    }

    p(OP.size());
    for(auto op : OP){
        cout << op.i0+1 << " " << op.j0+1 << " " << op.i1+1 << " " << op.j1+1 << endl;
    }

    
    
    return 0;
}

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

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

  vector<pair<long, long>> p(N);

  for (int i = 0; i < N; i++) {
    long long a;
    long long b;
    cin >> a >> b;
    p.at(i) = make_pair(b, a);
  }
  sort(p.begin(), p.end());

  long long lmt = 0;
  bool flag = true;
  for (int i = 0; i < N; i++) {
    long long a;
    long long b;
    tie(b, a) = p.at(i);
    lmt += a;
    if (lmt > b) flag = false;
  }

  if (flag)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

Measured memory_bytes: 3328
#include <iostream>
#include <utility>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
using namespace std;
using namespace boost;
using Graph = adjacency_list<listS, vecS, directedS, no_property, property<edge_weight_t, int>>;
using Edge = pair<int, int>;
using Vertex = boost::graph_traits<Graph>::vertex_descriptor;

int solve() {
  int N, M, u, v, from, to;
  vector<Edge> edge;
  
  cin >> N >> M;
  for (int i = 0; i < M; i++) {
    cin >> u >> v; u--; v--;
    edge.push_back(make_pair(u, N+v));
    edge.push_back(make_pair(N+u, 2*N+v));
    edge.push_back(make_pair(2*N+u, v));
  }
  cin >> from >> to; from--; to--;

  vector<int> weight(edge.size(), 1);

  // make graph
  Graph graph(edge.begin(), edge.end(), weight.begin(), 3 * N);

  // dijkstra
  vector<Vertex> parents(num_vertices(graph));
  dijkstra_shortest_paths(graph, from, predecessor_map(&parents[0]));

  // no path
  if (parents[to] == to) return -1;

  int cnt = 0;
  for (Vertex v = to; v != from; v = parents[v]) cnt++;
  return cnt / 3;
}

int main() {
  cout << solve() << endl;
}

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

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 

#define ll long long
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mp make_pair
#define pu push
#define pp pop_back
#define in insert
#define ld long double
#define forn(low,high,i) for(i = low;i < high;i++)
#define forrev(high,low,i) for(i = high; i >= low;i--)
#define all(v) v.begin(),v.end()
#define sz(v) (int)v.size()
#define line cout << __LINE__;
#define prv(a) for(auto x : a) cout << x << ' ';cout << '\n';
#define prvp(a) for(auto x : a) cout << "{" << x.ff << ',' << x.ss << "}";cout << '\n';
#define decimal_digits cout << fixed << setprecision(15);
string to_string(string s) { return '"' + s + '"';}
string to_string(char s) { return string(1, s);}
string to_string(const char* s) { return to_string((string) s);}
string to_string(bool b) { return (b ? "true" : "false");}
template <typename A> string to_string(A);
template <typename A, typename B>string to_string(pair<A, B> p) {return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}
template <typename A> string to_string(A v) {bool f = 1; string r = "{"; for (const auto &x : v) {if (!f)r += ", "; f = 0; r += to_string(x);} return r + "}";}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) {cerr << " " << to_string(H); debug_out(T...);}
#define pr(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

typedef unordered_map<int,int> umi;
typedef unordered_map<ll,ll> uml;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int inf = 1e9;
const ll INF = 1e18;
const int mod = 1e9 + 7;
const int bit32 = log2(inf) + 3;
const int bit64 = log2(INF) + 3;

inline int add(int a, int b){a += b; if(a >= mod) a -= mod; return a;}
inline int sub(int a, int b){a -= b; if(a < 0) a += mod; return a;}
inline int mul(int a, int b){return (int)((long long) a * b % mod);}
inline int modexpo(int a, int b){int res = 1; while(b > 0){ if(b & 1) res = mul(res, a); a = mul(a, a); b /= 2;} return res;}
inline int divide(int a, int b){ return mul(a, modexpo(b, mod - 2));}

clock_t time_p = clock();

void ktj(){
  time_p = clock() - time_p;
  cerr << "Time elapsed : " << (float)(time_p)/CLOCKS_PER_SEC << "\n";
}

void pre(){ // Reset each global variable (esp. for graphs)
  
}

void solve(){
  ll n, k, i, j;
  cin >> n >> k;
  priority_queue<ll> pq;
  for(i = 0; i < n; i++){
    ll x; cin >> x; pq.push(x);
  }
  while(!pq.empty() and k > 0){
    ll t = pq.top(); pq.pop(); k--;
  }
  ll sum = 0;
  while(!pq.empty()){
    sum += pq.top(); pq.pop();
  }
  cout << sum << '\n';
}

int main(){
  fastio

  pre();

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

  ktj();
}


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

#define pb push_back
#define fi first
#define se second
typedef long long ll;

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

	int n;
	cin >> n;
	int A[n];
	ll ans = 0;
	for (int i = 0; i < n; ++i)
		cin >> A[i];
	for (int i = 0; i < n; ++i)
		for (int j = i + 1; j < n; ++j)
			ans += (A[i] * A[j]);
	cout << ans << '\n';
}


Measured memory_bytes: 256
N, W = gets.split(" ").map(&:to_i)
dp = Array.new(W+1,0)
N.times{|i|
    w, v = gets.split(" ").map(&:to_i)
    dp_tmp = dp.clone
    (w..W).each{|j|
      dp_tmp[j] = dp[j-w] + v if dp[j - w] + v > dp[j] 
    }
    dp = dp_tmp
}
puts dp[W]

Measured memory_bytes: 69004
N = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(N[int(input())-1])

Measured memory_bytes: 38384
/*  -*- coding: utf-8 -*-
 *
 * c.cc: C - Successive Subtraction
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>

using namespace std;

/* constant */

const int MAX_N = 100000;

/* typedef */

typedef pair<int,int> pii;

/* global variables */

int as[MAX_N];
pii ps[MAX_N];

/* subroutines */

/* main */

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

  for (int i = 0; i < n; i++) scanf("%d", as + i);
  sort(as, as + n);

  int k = n - 2;
  while (k > 0 && as[k] > 0) k--;

  int m = 0;
  for (int j = n - 2; j > k; j--) {
    ps[m++] = pii(as[k], as[j]);
    as[k] -= as[j];
  }

  for (; k >= 0; k--) {
    ps[m++] = pii(as[n - 1], as[k]);
    as[n - 1] -= as[k];
  }

  printf("%d\n", as[n - 1]);
  for (int i = 0; i + 1 < n; i++)
    printf("%d %d\n", ps[i].first, ps[i].second);

  return 0;
}


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

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define FOR(i, a, b) for(int i = a; i < (int)b; ++i)
#define rrep(i, n) for(int i = ((int)n - 1); i >= 0; --i)

typedef long long ll;

const int Inf = 1e9;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int cnt = 0;
    rep (i, s.size()) if (s[i] == 'o') cnt++;
    if (15 - s.size() + cnt >= 8) cout << "YES" << endl;
    else cout << "NO" << endl;
    
    return 0;
}



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

int main(int argc, char const *argv[])
{
    int a, b, c, d, e, k;
    cin >> a >> b >> c >> d >> e >> k;

    if (e - a > k)
    {
        cout << ":("
             << "\n";
    }
    else
    {
        cout << "Yay!"
             << "\n";
    }

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
#define eb emplace_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mo 1000000007
#define MA 10e17
 ll int val[1000004]={0};
using namespace std;
//Conditional Operator (condition?true part:false part) eg : cout<<(y<=3?"YES":"NO")<<endl;
//string s(3,'1');
ll getmul(ll n){ll int k{0};while(n>0){k+=n%10;n=n/10;}return k;}//Sum OF n DIGITS
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t{1};
  //  cin>>t;
    while(t--){
        ll int n,d;
        cin>>n>>d;
        ll int arr[n][2];
        for(int i=0;i<n;i++)
            cin>>arr[i][0]>>arr[i][1];
        ll int ans{0};
        for(int i=0;i<n;i++){
           ll int x=arr[i][0],y=arr[i][1];
           ll int z=ceil(sqrt((x*x)+(y*y)));
            if(z<=d)
                ans++;
        }
        cout<<ans<<endl;
    }
 return 0;
}

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


int main()
{
    string s;
    cin>>s;
    int flg=0;
for(int i=0;i<s.length();i++)
{
      if(s[i] == '7')
      {
          flg=1;
          break;
      }

}
if(flg)
    cout<<"Yes\n";
else
    cout<<"No\n";
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  int The_sum =0;
  int sabun = 0;
  int max = 0;
  for(int i = 0;i >= 0;i++){
    if(N < pow(10,i)){
      max = i;
      break;
    }
  }
  for(int i = max;i>0;i--){
    int x = (N-sabun)/pow(10,(i-1));
    The_sum += x;
    sabun += x*pow(10,(i-1));
  }
  if(N%The_sum == 0){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

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

void solve() {

    int A,B,C,D,E,F;

    cin >> A >> B >> C >> D >> E >> F ;

    int a=100*A,b=100*B;

    vector<int> water(0),sugar(0);

    for(int i=0;a*i<=F;i++){
        for(int j=0;b*j<=F;j++){
            water.push_back(a*i+b*j);
        }
    }

    for(int i=0;C*i<=F;i++){
        for(int j=0;D*j<=F;j++){
            sugar.push_back(C*i+D*j);
        }
    }

    double conmax=0;

    int w=100,s=1;

    for(int i=0;i<water.size();i++){
        for(int j=0;j<sugar.size();j++){

            if(water.at(i)==0&&sugar.at(j)==0) continue;

            if(water.at(i)+sugar.at(j)<=F && sugar.at(j)<=water.at(i)*E/100.0){//Fを越えてないか　溶け残りがないか

                double con = 100.0*sugar.at(j)/(water.at(i)+sugar.at(j));   // ここをint計算しててハマった。100.0などを紛れ込ませてdoubleに変換

                if(con >= conmax) {
                    w = water.at(i)+sugar.at(j); s = sugar.at(j);
                    conmax = con;
                }

            }

        }
    }

    cout << w << " " << s <<endl;
}

int main() {
    solve();
//    int a, b, c, d, e, f;
//    cin >> a >> b >> c >> d >> e >> f;
//
//    double max_m = 0;
//    int max_beaker = 100;
//    int max_s = 0;
//    for (int i = 0; a * 100 * i <= f; ++i) {
//        int wA = i * a * 100;
//        for (int j = 0; wA + b * 100 * j <= f; ++j) {
//            int wB = j * 100 * b;
//            int w = wA + wB;
//            if (0 == w || f < w) continue;
//            for (int k = 0; w + (c * k) <= f; ++k) {
//                int sC = k * c;
//                for (int l = 0; w + sC + (d * l) <= f; ++l) {
//                    int sD = d * l;
//                    int s = sC + sD;
//                    int acc = w + s;
//                    double m = (double)s / (double)acc;
//                    if ((100 * s <= e * w) && max_m < m) {
//                        max_m = m;
//                        max_beaker = acc;
//                        max_s = s;
//                    }
//                }
//            }
//        }
//    }
//    cout << max_beaker << " " << max_s << endl;
    return 0;
}


Measured memory_bytes: 2420
N = int(input())
H = list(map(int, input().split()))

result = "Yes"

for i in range(0, N-1):
  if H[i] >= H[i+1]:
    if i == 0:
      H[i] -= 1
    elif i >= 1 and H[i-1] < H[i]:
      H[i] -= 1
  
  if H[i] > H[i+1]:
    result = "No"
    break

print(result)

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

using namespace std;
using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;

#define INF (1LL << 60)
#define MOD 1000000007
#define PI 3.14159265358979323846

#define REP(i,m,n) for(ll (i)=(m),(i_len)=(n);(i)<(i_len);++(i))
#define FORR(i,v) for(auto (i):v)
#define ALL(x) (x).begin(), (x).end()
#define PR(x) cout << (x) << endl
#define PS(x) cout << (x) << " "
#define SZ(x) ((ll)(x).size())
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define ASC(x) sort(ALL((x)))
#define DESC(x) sort(ALL((x)),greater<ll>())
#define REV(x) reverse(ALL((x)))
#define pb push_back



vector<pair<ll,ll>> pfact(ll n)
{
    vector<pair<ll,ll>> pf;
    ll t = n, cnt;
    
    for(ll i=2; i*i<=t; ++i) {
        cnt = 0;
        if(t % i != 0) continue;
        while(t % i == 0) {
            t /= i;
            ++cnt;
        }
        pf.pb(make_pair(i, cnt));
    }
    
    if(t != 1) pf.pb(make_pair(t, 1));
    
    return pf;
}


ll modpow(ll a, ll n, ll m)
{
    if(n == 0) return 1;
    ll t = modpow(a, n >> 1, m);
    t = t * t % m;
    if(n & 1) t = t * a % m;
    return t; 
}

ll modinv(ll a, ll m)
{
    return modpow(a, m - 2, m);
}

int main()
{
    ll N;
    cin >> N;
    vec A(N);
    REP(i,0,N) cin >> A[i];

    ASC(A);

    vector<vector<pair<ll,ll>>> P(N);
    vec e_max(A[N-1]+1, 0);
    REP(i,0,N) {
        P[i] = pfact(A[i]);
        FORR(p,P[i]) {
            e_max[p.first] = MAX(e_max[p.first],p.second);
        }
    }

    ll L = 1;
    REP(i,0,A[N-1]+1) {
        L = (L * (e_max[i] > 0 ? modpow(i, e_max[i], MOD) : 1)) % MOD;
    }

    ll sum = 0, prod;
    REP(i,0,N) {
        prod = L;
        FORR(p,P[i]) {
            prod = (prod * modpow(modinv(p.first, MOD), p.second, MOD)) % MOD;
        }
        sum = (sum + prod) % MOD;
    }

    PR(sum);
    
    return 0;
}

/*



*/

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

int main(){
    using namespace std;
    unsigned long N, K;
    cin >> N >> K;
    vector<unsigned long> p(N);
    for(auto&& i : p){
        cin >> i;
        --i;
    }
    const auto& perm_mul = [](vector<unsigned long>& x, const vector<unsigned long>& p) -> void {
        vector<unsigned long> k(x), r(p);
        transform(k.begin(), k.end(), x.begin(), [&r](auto i){return r[i];});
    };
    const auto& perm_pow = [&perm_mul](const vector<unsigned long>& _a, unsigned long n) -> vector<unsigned long> {
        vector<unsigned long> r(_a.size()), a(_a);
        iota(r.begin(), r.end(), 0UL);
        while(n){
            if(n & 1)perm_mul(r, a);
            perm_mul(a, a);
            n >>= 1;
        }
        return r;
    };
    cout << perm_pow(p, K)[0] + 1 << endl;
    return 0;
}

Measured memory_bytes: 11180
<?php
    $n = intval(trim(fgets(STDIN)));
    $a = explode(" ", trim(fgets(STDIN)));
    $c = 0;

    for ($i = 0; $i < $n; $i++) {
        for ($j = $n - 1; $j > $i; $j--) {
            if ($a[$j] < $a[$j - 1]) {
                $w = $a[$j - 1]; 
                $a[$j - 1] = $a[$j];
                $a[$j] = $w; 
                $c++;
            }   
        }   
    }   

    $s = implode(" ", $a);
    echo $s . "\n";
    echo $c . "\n";


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

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


int main() {
	int n;
	string s;
	cin >> n >> s;
	rep(i, s.size()) {
		if ('Z' - s.at(i) < n) {
			s.at(i) = n - 'Z' + s.at(i) + 'A' - 1;
		}
		else {
			s.at(i) += n;
		}
		cout << char(s.at(i));
	}

}

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

int main() {

    int n, m, t, prev = 1, curr, ans = 0;
    scanf("%d %d", &n, &m);

    scanf("%d", &curr);
    if (curr > 1) {
        ans = curr - 1;
        prev = curr;
    }
    for (int i = 1; i < m; i++) {
        scanf("%d", &curr);
        t = (curr - prev) / 2;
        ans = max(ans, t);
        prev = curr;
    }
    if (prev < n) {
        t = n - prev;
        ans = max(ans, t);
    }
    printf("%d\n", ans);
    return 0;
}



Measured memory_bytes: 2760
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<n; ++i)
#define rep1(i, n) for (int i=1; i<=n; ++i)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
constexpr ll  MOD = (1e9+7);
constexpr int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
constexpr int lcm(int a, int b) { return a / gcd(a, b) * b; }

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;
}
ll factorial(ll n, ll m=2) {
    // calculate n!
    m = max(2LL, m);
    ll rtn = 1;
    for (ll i=m; i<=n; i++) {
        rtn = (rtn * i) % MOD;
    }
    return rtn;
}
ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
ll modpow(ll a, ll n) {
    ll res = 1;
    while (n > 0) {
        if (n & 1)
            res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int k, a, b; cin >> k >> a >> b;
    for (int i=a; i<=b; ++i) {
        if (i%k==0) {
            puts("OK");
            return 0;
        }
    }
    puts("NG");
    return 0;
}

Measured memory_bytes: 3652
def calcs(x,y,ax,ay,bx,by) ((ax-x)*(by-y)-(bx-x)*(ay-y))/2.0 end
def inpf() a=gets.chomp.split(" ").map(&:to_f)end
def inps() a=gets.chomp.split(" ")end  
def copy(a) Marshal.load(Marshal.dump(a)) end
def factorial(n)(n < 2)? 1 : (2..n).inject(:*) end
def scount(a) b=na(a.max+1);a.each{|n|b[n]+=1};return b end
def na(n,d=0) Array.new(n,d)end
def na2(n,m,d=0) Array.new(n){Array.new(m,d)}end
def na3(n,m,l,d=0) Array.new(n){Array.new(m){Array.new(l,d)}}end
def bit(n) n.to_s(2).split("").map(&:to_i) end
def inp() a=gets.chomp.split(" ").map(&:to_i)end

n=inp[0]
a = inp
h = {}
a.each.with_index do |d,i|
  a[i] = d-i
  d = a[i]
  if h[d]
    h[d] += 1 
  else
    h[d] = 1
  end
end
sum = 0
m = a.sort[n/2]
a.each do |d|
  sum += (d - m).abs
end
p sum

Measured memory_bytes: 34064
n = int(input())
table = [0 for i in range(100000)]

a = list(map(int, input().split()))
s = sum(a)

for e in a:
    table[e-1] += 1

q = int(input())

for p in range(q):
    b, c = map(int, input().split())
    s += (c - b) * table[b-1]
    table[c-1] += table[b-1]
    table[b-1] = 0
    print(s)


Measured memory_bytes: 21992
#include <stdio.h>

int main(void)
{
	int train[100];
	int ans[100];
	int a, b, c;
	a = 0;
	c = 0;
	while (scanf("%d", &train[a]) != EOF){
		b = a;
		if (train[a] == 0) {
			train[a] = -1;
			while (b != 0) {
				b--;
				if (train[b] != -1) {
					ans[c] = train[b];
					train[b] = -1;
					c++;
					b = 0;
				}
			}
		}
		a++;
	}
	for (b = 0; b < c; b++) {
		printf("%d\n", ans[b]);
	}
	
	return (0);
}	
					

Measured memory_bytes: 600
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define fi first
#define se second
#define endl "\n"

template<typename T> inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){
	int len=d.size();
	rep(i,len){
		s<<d[i];if(i<len-1) s<<" ";
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){
	int len=d.size();
	rep(i,len){
		s<<d[i]<<endl;
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){
	s<<"{ ";
	for(auto itr=v.begin();itr!=v.end();++itr) {
		if (itr!=v.begin()) {s<< ", ";}
		s<<(*itr);
	}
	s<<" }";
	return s;
}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){
	s<<"{"<<endl;
	for(auto itr=m.begin();itr!=m.end();++itr){
		s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;
	}
	s<<"}"<<endl;
	return s;
}

const ll mod=1e9+7;
const ll inf=1e17;
const int INF=1e9;
const double PI=acos(-1);
const double EPS=1e-10;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,m;
	cin>>n>>m;
	vector<vector<int>> g(n);
	rep(i,m){
		int s,t;
		cin>>s>>t;
		s--,t--;
		g[s].push_back(t);
	}
	double ans=inf;
	rep(i,n){
		if(g[i].size()==1) continue;
		vector<double> dp(n,0);
		for(int j=n-2;j>=0;j--){
			vector<double> now;
			for(auto v:g[j]) now.push_back(dp[v]);
			if(j==i){
				sort(begin(now),end(now)); 
				rep(k,now.size()-1) dp[j]+=now[k];
				dp[j]/=(double)(now.size()-1);
			}else{
				rep(k,now.size()) dp[j]+=now[k];
				dp[j]/=(double)now.size();
			}
			dp[j]++;
		}
		chmin(ans,dp[0]);
	}
	cout<<setprecision(10)<<ans<<endl;
}

Measured memory_bytes: 1408
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; i++)

int N, M;
int P[1000000], Y[1000000];
vector<int> yd[100001];

int main()
{
  cin >> N >> M;
  rep(i, M) cin >> P[i] >> Y[i], yd[P[i]].push_back(Y[i]);
  rep(i, N) sort(yd[i + 1].begin(), yd[i + 1].end());
  rep(i, M) printf("%012lld\n", ll(P[i]) * 1000000 + int(lower_bound(yd[P[i]].begin(), yd[P[i]].end(), Y[i]) - yd[P[i]].begin()) + 1);

  return 0;
}


Measured memory_bytes: 10752
h,w=map(int,raw_input().split())
a=[map(int,raw_input().split()) for _ in xrange(h)]
dp=[[[0]*(h+1) for _ in xrange(w+1)] for _ in xrange(h+1)]

for i in xrange(h):
    for j in xrange(w):
        for k in xrange(h):
            if i+j-k<=-1 or i+j-k>=w:
                continue
            if i==k:
                dp[i+1][j+1][k+1]=max(dp[i][j+1][k+1],dp[i+1][j][k+1],dp[i][j+1][k],dp[i+1][j][k])+a[i][j]
            else:
                dp[i+1][j+1][k+1]=max(dp[i][j+1][k+1],dp[i+1][j][k+1],dp[i][j+1][k],dp[i+1][j][k])+a[i][j]+a[k][i+j-k]

print(dp[h][w][h])

Measured memory_bytes: 93212
#include<bits/stdc++.h>
#define N 300005
using namespace std;
int n,a[N];
inline bool check(int l,int r){
	int mx=0,mn=n+1;
	for(int i=l;i<=r;++i)mx=max(mx,a[i]),mn=min(mn,a[i]);
	if(mx!=r||mn!=l)return false;
	int mx1=0,mx2=0;
	for(int i=l;i<=r;i+=2){
		if(mx1<a[i]&&mx2<a[i])mx1=a[i];
		else if(mx2<a[i])mx2=a[i];
		else return false;
	}
	return true;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]);
	for(int i=1;i<=n;++i){
		if(a[i]==i)continue;
		int p=i;
		while(p<=n-2){if(a[p+1]!=p+1||a[p+2]==p+2)break;p+=2;}
		if(!check(i,p)){puts("No");return 0;}
		i=p;
	}
	puts("Yes");
	return 0;
}

Measured memory_bytes: 1408
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
S=sum(A)
OK=S/(4*M)
ans=0
for i in range(M):
  if A[i]>=OK:
    ans+=1
if ans==M:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3064
# include <bits/stdc++.h>
  typedef long long ll;
#define pii  pair<int,int>
#define vpii vector<pii>
#define vll  vector<ll>
#define vi  vector<int>
#define pb push_back
#define f  first
#define s  second
#define all v.begin(),v.end()
#define fio ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
typedef unsigned long long ulll;
 
using namespace std ;
int main () {

  string s;
  cin>>s;
  string  st = s;
  reverse(s.begin(),s.end());
  
  if(st==s)
  cout<<"Yes";
  
  else
    cout<<"No";
   
  return 0;
}

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

int main(){
  int a,b,y;
  double x;
  cin >> a >> b;
  x = a + b;
  x /= 2;
  y = (a + b) / 2;
  if(x - y == 0.5){
   y += 1;
   cout << y << endl;
  }
  else if(x - y == 0){
    cout << y << endl;
  }
  else{
    cout << "error" << endl; 
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<functional>
#include<queue>
#include <iomanip>
#include<map>
#include<limits>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<utility>
#include<complex>
#include<cstdlib>
#include<set>
#include<cctype>

#define DBG cerr << '!' << endl;
#define REP(i,n) for(int (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(int (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(int (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int i = 0;i < (n);i++)cerr << v[i] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()

using namespace std;

typedef long long ll;
typedef vector<int> iv;
typedef vector<iv> iiv;
typedef vector<string> sv;

vector<vector<bool> > A(51,vector<bool>(51));
vector<vector<bool> > B(51,vector<bool>(51));
vector<vector<bool> > C(51,vector<bool>(51));
vector<vector<bool> > Y(51,vector<bool>(51));
vector<vector<bool> > mp(51,vector<bool>(51));

int main()
{
	int n,m,a,b,c;
	cin >> n >> m>> a >> b >> c;
	
	REP(i,m)
	{
		int u,v;
		cin >> u >> v;
		u--;v--;
		mp[u][v] = true;
	}
	
	Y = mp;
	REP(i,max(a,max(b,c)))
	{
		vector<vector<bool> > Z(51,vector<bool>(51));

		if(i+1 == a)A = Y;
		if(i+1 == b)B = Y;
		if(i+1 == c)C = Y;


		REP(i,n)REP(j,n)REP(k,n)
		{
			Z[i][j] = Z[i][j] | ( Y[i][k] & mp[k][j]);
		}
		Y = Z;
	}
	
	//SHOW2d(A,n+1,n+1);
	//SHOW2d(B,n+1,n+1);
	//SHOW2d(C,n+1,n+1);
	
	set<int> goal;
	goal.insert(n-1);
	
	for(int ans = 1;;ans++)
	{
		set<int> nw;
		REP(i,n)
		{
			if(!goal.count(i))
			{
				bool aa = false;
				bool bb = false;
				bool cc = false;
				REP(j,n)
				{
					if(goal.count(j))
					{
						if(A[i][j])aa = true;
						if(B[i][j])bb = true;
						if(C[i][j])cc = true;
					}
				}
				if(aa&&bb&&cc)nw.insert(i);
			}
		}
		
		if(nw.empty())
		{
			cout << "IMPOSSIBLE" << endl;
			return 0;
		}
		
		goal.insert(ALL(nw));
		if(goal.count(0))
		{
			cout << ans << endl;
			return 0;
		}
	}
	
	return 0;
}

Measured memory_bytes: 3136
#include<iostream>
using namespace std;
int main(){
    string S;
    cin >> S;
    if(S[0] == 'S'){
        cout << "Cloudy" << endl;
    }
    else if(S[0] == 'C'){
        cout << "Rainy" << endl;
    }
    else{
        cout << "Sunny" << endl;
    }
    
    
    
    
    
    
    
    
    
}

Measured memory_bytes: 3484
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>

#include <sstream>

using namespace std;

void printCoffo(double x1, double y1, double x5, double y5, int n){

  if(n<=0){
    return;
  }
  double x2,y2,x3,y3,x4,y4;
  x2 = (2.0*x1+x5)/3.0;
  y2 = (2.0*y1+y5)/3.0;
  x4 = (x1+2.0*x5)/3.0;
  y4 = (y1+2.0*y5)/3.0;

  x3 = x2 + (x4-x2)/2.0 - sqrt(3.0)*(y4-y2)/2.0;
  y3 = y2 + sqrt(3.0)*(x4-x2)/2.0 + (y4-y2)/2.0;

  printCoffo(x1, y1, x2, y2, n-1);
  cout << x2 << " " << y2 <<endl;
  printCoffo(x2, y2, x3, y3, n-1);
  cout << x3 << " " << y3 << endl;
  printCoffo(x3, y3, x4, y4, n-1);
  cout << x4 << " " << y4 << endl;
  printCoffo(x4, y4, x5, y5, n-1);
  
}
  

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

  double x1,y1,x2,y2;
  x1 = 0.0;
  y1 = 0.0;
  x2 = 100.0;
  y2 = 0.0; 

  cout << x1 << " " << y1 << endl;
  printCoffo(x1, y1, x2, y2, n);
  cout << x2 << " " << y2 << endl;
  
}

Measured memory_bytes: 1252
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int main(){
	int dp[1000][2][2][2][2]={};
	string n;
	cin>>n;
	if(n.size()==1000)
		n=string(999,'9');
	dp[0][0][0][0][0]=1;
	for(int i=0;i<n.size();i++)
		for(int smaller=0;smaller<2;smaller++)
			for(int has3=0;has3<2;has3++)
				for(int has5=0;has5<2;has5++)
					for(int has7=0;has7<2;has7++)
						for(int x=3;x<=min(smaller?9:n[i]-'0',7);x+=2)
							(dp[i+1][smaller||x<n[i]-'0'][has3||x==3][has5||x==5][has7||x==7]+=dp[i][smaller][has3][has5][has7])%=mod;
	long long ans=(dp[n.size()][0][1][1][1]+dp[n.size()][1][1][1][1])%mod,pow3=27,pow2=8;
	for(int i=3;i<n.size();i++){
		(ans+=pow3-3*pow2+3+mod)%=mod;
		(pow3*=3)%=mod;
		(pow2*=2)%=mod;
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 256