akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

#define rep(n) for(int i=0;i<n;i++)
#define repp(j, n) for(int j=0;j<n;j++)
#define reppp(i, m, n) for(int i=m;i<n;i++)
#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define debug(x) cerr << #x << ": " << x << endl;

using namespace std;

typedef long long ll;
typedef pair<ll, ll> Pll;
typedef pair<int, int> Pii;
struct edge{int from, to; ll cost;};

ll wf[51][51];
int n;
int a[50], b[50];

void floyd_warshall(set<int> st){
    fill((ll *)wf[0], (ll *)wf[51], LLONG_MAX);

    for(int k: st){
        repp(n, 51){
            wf[n][n%k] = min(wf[n][n%k], (1LL << k));
        }
    }

    repp(k, 51){
        repp(i, 51){
            repp(j, 51){
                if(wf[i][k] == LLONG_MAX || wf[k][j] == LLONG_MAX) continue;
                wf[i][j] = min(wf[i][j], (wf[i][k]|wf[k][j]));
            }
        }
    }
}

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

    cin >> n;
    rep(n) cin >> a[i];
    rep(n) cin >> b[i];

    int same = 1, max_a = -1, max_b = -1;
    rep(n){
        if(a[i] != b[i]) same = 0;
        max_a = max(max_a, a[i]);
        max_b = max(max_b, b[i]);
    }
    if(same){
        cout << 0 << endl;
        return 0;
    }
    if(max_b == 0){
        cout << 2 << endl;
        return 0;
    }

    set<int> st; // 同じ数で2回剰余とっても意味ない，使うのは1回だ毛で使用順を変えれば良いだけ
    reppp(i, 1, 51) st.insert(i);
    
    int use = 0;
    ll ans = 0LL;
    floyd_warshall(st);
    rep(n){
        if(wf[a[i]][b[i]] == LLONG_MAX){
            use = 1;
            break;
        }
    }
    if(use){
        cout << -1 << endl;
        return 0;
    }

    for(int l=50;l>=1;l--){
        int use = 0;
        st.erase(l);
        floyd_warshall(st);
        rep(n){
            if(wf[a[i]][b[i]] == LLONG_MAX){
                use = 1;
                break;
            }
        }
        if(use){
            ans |= 1LL << l;
            st.insert(l);
        }
    }

    cout << (ans?ans:-1) << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
char a[15];
int te2=1000;
cin>>a;
int l=strlen(a);
for(int i=0;i<l-2;i++)
{
    int te=((a[i]-48)*10+a[i+1]-48)*10+a[i+2]-48;
    int  x=abs(te-753);
    if(x<te2)
    {
        te2=x;
    }
}
cout<<te2<<endl;
return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
 
using namespace std;
 
typedef long long ll;
const ll nmax = 1e9 + 7;
const ll mod = 998244353;
const double PI = 2 * asin(1);

int main() {
    string S;
    cin >> S;

    string Y = S.substr(0, 4);
    int y = atoi(Y.c_str());
    string M = S.substr(5, 2);
    int m = atoi(M.c_str());
    string D = S.substr(8, 2);
    int d = atoi(D.c_str());

    if (m <= 4) {
        cout << "Heisei" << endl;
    } else {
        cout << "TBD" << endl;
    };
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i=0;i<n;++i)

typedef long long ll;
using namespace std;
int main(){
    cin.tie(0);
   	ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int cnt = 0;
    REP(i, s.length()){
        if(s[i]=='o')++cnt;
    }
    if(cnt+15-s.length()>=8){
        cout << "YES" << "\n";
    } else {
        cout << "NO" << "\n";
    }
    return 0;
}

Measured memory_bytes: 256
use std::io;

fn read_input() -> String {
    let mut s = String::new();
    io::stdin().read_line(&mut s);
    s
}

fn wa() {
    println!("WA");
    std::process::exit(0);
}

fn solve(s: String) {
    let mut c = 0;
    for (i, j) in s.chars().enumerate() {
        match (i, j) {
            (0, 'A') => (),
            (i, 'C') if i == 1 || i >= s.len() - 2 || c == 1 => wa(),
            (_, 'C') => c += 1,
            (0, _) | (_, 'A'...'Z') => wa(),
            (_, _) => (),
        }
    }
    if c == 0 {
        wa();
    }
    println!("AC");
}

fn main() {
    solve(read_input());
}


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

using namespace std;

typedef long long int ll;
typedef long double ld;

int main() {
    //freopen("input.txt", "r", stdin);

    int a, b, c;
    cin >> a >> b >> c;

    int x = 100 * a + 10 * b + c;

    if(x % 4 == 0) {
        cout << "YES";
    } else {
        cout << "NO";
    }
    cout << "\n"; return 0;
}


Measured memory_bytes: 256
n = int(input())
a = [int(input()) for i in range(n)]

ans = 0
for i in range(n):
    ans ^= a[i]

set_ = set()
for i in range(n):
    set_.add(a[i] ^ (a[i] - 1))
 
cnt = 0
for i in range(50)[::-1]:
    if ans & (1 << i):
        cnt += 1
        if (1 << (i + 1)) - 1 in set_:
            ans ^= (1 << (i + 1)) - 1
        else:
            print(-1)
            exit()
print(cnt)

Measured memory_bytes: 49624
using System;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Linq;

public static partial class Program
{
    //テンプレここから
    public static int ToInt(this string str)
    {
        return int.Parse(str);
    }

    public static long ToLong(this string str)
    {
        return long.Parse(str);
    }
    public static IEnumerable<int> ToInt(this string[] strs)
    {
        return strs.Select(x => x.ToInt());
    }

    public static IEnumerable<long> ToLong(this string[] strs)
    {
        return strs.Select(x => x.ToLong());
    }
    public static IEnumerable<int> SplToInt(this string str, char opr = ' ')
    {
        return str.Split(opr).ToInt();
    }

    public static IEnumerable<long> SplToLong(this string str, char opr = ' ')
    {
        return str.Split(opr).ToLong();
    }
    public static string CRL()
    {
        return Console.ReadLine();
    }
    public static void CWL(object obj)
    {
        Console.WriteLine(obj);
    }
    public static int Diff(int a, int b)
    {
        return Math.Abs(Math.Max(a, b) - Math.Min(a, b));
    }
    public static long Diff(long a, long b)
    {
        return Math.Abs(Math.Max(a, b) - Math.Min(a, b));
    }
    public static int Sign(this int i)
    {
        return Math.Sign(i);
    }

    public static bool IsEven(this int i)
    {
        return i % 2 == 0;
    }
    //テンプレここまで
}

public static partial class Program
{
    static void Main()
    {
        var abc = CRL().SplToInt().ToArray();
        var max = abc.Max();

        if (max.IsEven() != abc.Sum().IsEven())
        {
            max++;
        }

        var count = 0;
        foreach (var i in abc)
        {
            count += max - i;
        }

        CWL(count / 2);
    }
}

Measured memory_bytes: 13396
#include<iostream>
#include<string>
#include<map>
using namespace std;
char change(char a){
	if(a=='p') return 'q';
	if(a=='q') return 'p';
	if(a=='b') return 'd';
	return 'b';
	
 }
string change(string a){
    int len=a.length();
    
    for(int i=0;i<len/2;++i){
        swap(a[i],a[len-1-i]);
    }
    for(int i=0;i<len;++i){
        a[i]=change(a[i]);
    }
    return a;
}
int main(){
    string s;
    cin>>s;
    if(s==change(s)) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

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

template <class T>
inline void read(T &res)
{
	res = 0; bool bo = 0; char c;
	while (((c = getchar()) < '0' || c > '9') && c != '-');
	if (c == '-') bo = 1; else res = c - 48;
	while ((c = getchar()) >= '0' && c <= '9')
		res = (res << 3) + (res << 1) + (c - 48);
	if (bo) res = ~res + 1;
}

template <class T>
inline T Min(const T &a, const T &b) {return a < b ? a : b;}

typedef long long ll;

const int N = 20;

int n, a[N];
std::map<ll, ll> f[N][N];

ll F(int l, int r, int x, int y)
{
	ll orz = 20050131ll * x + y;
	if (f[l][r].count(orz)) return f[l][r][orz];
	if (l + 1 == r) return f[l][r][orz] = 1ll * a[l] * x + 1ll * a[r] * y;
	ll res = 1145141919810114514ll;
	for (int mid = l + 1; mid < r; mid++)
		res = Min(res, F(l, mid, x, x + y) + F(mid, r, x + y, y)
			- 1ll * (x + y) * a[mid]);
	return f[l][r][orz] = res;
}

int main()
{
	read(n);
	for (int i = 1; i <= n; i++) read(a[i]);
	return std::cout << F(1, n, 1, 1) << std::endl, 0;
}

Measured memory_bytes: 36284
import itertools

N = int(input())
P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))


pos = 0
pos_p = 0
pos_q = 0
for i in itertools.permutations(range(1,N + 1)):
    pos += 1
    if i == P:
        pos_p = pos
    if i == Q:
        pos_q = pos

print(abs(pos_p - pos_q))

Measured memory_bytes: 3064
var toInt = x=>parseInt(x,10);
var toIntArr = arr=>arr.map(x=>toInt(x));
var abs = x=>x>0?x:-x;
function min(){var rest = arguments,val=rest[0];for(var i=1;i<rest.length;i++)if(rest[i]<val)val = rest[i];return val}
function max(){var rest = arguments,val=rest[0];for(var i=1;i<rest.length;i++)if(rest[i]>val)val = rest[i];return val}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));
 
function Main(input){
	var input = input.split('\n');
	var s = input[0];
	var n = s.length;
	var isC = 0;
	if(s[0]!=='A'){
		console.log('WA');
		return 0;
	}
	if(s[1]!==s[1].toLowerCase() || s[n-1]!==s[n-1].toLowerCase()){
		console.log('WA');
		return 0;
	}
	for(var i = 2; i < n-1; i++){
		if(s[i]!==s[i].toLowerCase()){
			if(s[i]==='C'){
				if(isC===1){
					console.log('WA');
					return 0;
				}else{
					isC++;
				}
			}else{
				console.log('WA');
				return 0;
			}
		}
	}
	if(isC===0){
		console.log('WA');
	}else{
		console.log('AC');
	}
}

Measured memory_bytes: 21064
import java.util.* ;
class Main {
  public static void main(String[] args) {
    
    Scanner scan = new Scanner(System.in);
 int a= scan.nextInt();
     int b= scan.nextInt();
     int c= scan.nextInt();
    if(a+b >=c){
      System.out.println("Yes");
    }else{
      System.out.println("No");
    }
  	
  }
}


Measured memory_bytes: 22868
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
// Welcome to my source code!

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

int main() {
    int n, k;
    cin >> n >> k;
    int h[n];
    for (int i = 0; i < n; i++) cin >> h[i];
    sort(h, h+n, greater<int>());
    ll ans = 0;
    for (int i = k; i < n; i++) {
        ans += h[i];
    }
    cout << ans << endl;
}

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

using namespace std;

#define rep(i, a, b)  for(int i = (a); i < (b); i++)
#define rrep(i, a, b) for(int i = (a); i > (b); i--)
#define sq(x) ((x) * (x))
#define bit(x) bitset<8>(x)
#define vsort(v)  sort(v.begin(), v.end())
#define rvsort(v) sort(v.begin(), v.end(), greater<int>())
#define debug(x) cout << #x << " " << (x) << endl
#define ci cin
#define co cout
#define en endl
#define ln cout<< '\n'
#define pb push_back
#define fi first
#define se second
#define MOD 1e9+7

typedef long long int llint;
typedef pair<int, int> pii;
typedef pair<llint, llint> pll;
typedef vector<int> vi;
typedef vector<llint> vl;
typedef vector<pii> vii;
typedef vector<pll> vll;


template<typename Tn> Tn __lcm(Tn a, Tn b)
{
    return a / __gcd(a, b) * b;
}

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

int main()
{
    int n;
    int p[100];
    int s[100];

    ci >> n;
    rep(i, 0, n) {
	ci >> p[i];
	s[i] = p[i];
    }

    sort(s, s + n);
    
    int cnt = 0;
    rep(i, 0, n) if(p[i] != s[i]) cnt++;
    
    if(cnt <= 2) co << "YES" << en;
    else co << "NO" << en;
  
    return 0;
}


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

using namespace std;

int main(){
	int sum,ans=0;
	int n,a,b;
	scanf("%d%d%d",&n,&a,&b);
	for(int i=1;i<=n;i++)
	{
		int k=i;
		sum=0;
		while(k>=10)
		{
			sum+=k%10;
			k/=10;
		}
		sum+=k;
		if((sum>=a)&&(sum<=b))
		ans+=i;
	}
	cout<<ans;
	return 0;
}

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


#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
#define iout(x) printf("%d\n",x)
#define lout(x) printf("%lld\n",x)
#define REP(x,l,u) for(int x = (l);x<=(u);x++)
#define RREP(x,l,u) for(int x = (l);x>=(u);x--)
#define mst(x,a) memset(x,a,sizeof(x))
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define MP make_pair
#define se second
#define fi first
#define dbg(x) cout<<#x<<" = "<<(x)<<endl;
#define sz(x) ((int)x.size())
#define cl(x) x.clear()

typedef  long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
using namespace std;

const int maxn = 4010;
const int mod = 924844033;
const int MAX = 1000000010;
const double eps = 1e-6;
const double PI = acos(-1);

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> inline void read(A&x,B&y){read(x);read(y);}
template<typename A,typename B,typename C> inline void read(A&x,B&y,C&z){read(x);read(y);read(z);}
template<typename A,typename B,typename C,typename D> inline void read(A&x,B&y,C&z,D&w){read(x);read(y);read(z);read(w);}
template<typename A,typename B> inline A fexp(A x,B p){A ans=1;for(;p;p>>=1,x=1LL*x*x%mod)if(p&1)ans=1LL*ans*x%mod;return ans;}
template<typename A,typename B> inline A fexp(A x,B p,A mo){A ans=1;for(;p;p>>=1,x=1LL*x*x%mo)if(p&1)ans=1LL*ans*x%mo;return ans;}

int n,K,ans,t;

int f[maxn][maxn][2];

int fac[maxn],Is[maxn];

void Work(){
	fac[0]=1;
	REP(i,1,n)fac[i]=1ll*fac[i-1]*i%mod;
	for(int i=0,j=1;i<=n;i++,j=-j)ans=(1ll*j*(f[n*2][i][0]+f[n*2][i][1])*fac[n-i]%mod+ans+mod)%mod;
	iout(ans);
}

void Init(){
	read(n,K);
	REP(i,1,K)REP(j,0,1){
		int x=i;
		while(x<=n){
			t++;x+=K;
		}
		Is[t]=1;
	}
	f[1][0][0]=1;
	REP(i,1,n*2-1)REP(j,0,n){
		f[i+1][j][0]=(f[i][j][0]+f[i][j][1])%mod;
		if(!Is[i])f[i+1][j+1][1]=f[i][j][0];
	}
}

int main(){
	Init();
	Work();
	return 0;
}


Measured memory_bytes: 124672
import queue
q=queue.Queue()
n,m=map(int,input().split())
room=[]
singpost=[0]*(n+1)

for i in range(n+1):
    room.append([])

for _ in range(m):
    r1,r2=map(int,input().split())
    if r1==1 :
        singpost[r2]=1
        q.put(r2)
    elif r2==1:
        singpost[r1]=1
        q.put(r1)
    else:
        room[r1].append(r2)
        room[r2].append(r1)

while not(q.empty()):
    loca=q.get()
    for x in room[loca]:
        if singpost[x]==0:
            singpost[x]=loca
            q.put(x)

if singpost.count(0)>2:print("No")
else:
    print("Yes")
    for x in range(2,n+1):
        print(singpost[x])





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

namespace ABC066A
{
	class Program
	{
		static void Main(string[] args)
		{
			int a, b, c, s;
			string[] word = Console.ReadLine().Split(' ');

			a = int.Parse(word[0]);
			b = int.Parse(word[1]);
			c = int.Parse(word[2]);

			

			//A,B.Cの最大値を求める
			int m = a;
			if (b > m) m = b;
			if (c > m) m = c;
			//最大値を除く金額の和
			s = a + b + c - m;


			Console.WriteLine(s);


			//Console.ReadKey();
		}
	}
}

Measured memory_bytes: 27192
#include <stdio.h>
#include <math.h>
#include <queue>
#include <vector>
using namespace std;
 
int main()
{
    double a,b,c;
    int n,i;
    priority_queue< double, vector<double>, greater<double> > que;
 
    scanf("%d",&n);
 
    for(i = 0; i < n; i++){
        scanf("%lf %lf %lf",&a,&b,&c);
        que.push(a);
        que.push(b);
        que.push(c);
        a = que.top();
        que.pop();
        b = que.top();
        que.pop();
        if(pow( que.top(),2.0 ) == pow( a,2.0 ) + pow( b,2.0 )){
            printf("YES\n");
        }
        else{
            //printf("%lf %lf\n",pow( que.top(),2.0 ),pow( a,2.0 ) + pow( b,2.0 ));
            printf("NO\n");
        }
        que.pop();
    }
 
    return 0;
}

Measured memory_bytes: 1064
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while (in.hasNext()) {
			double xa1 = in.nextDouble();
			double ya1 = in.nextDouble();
			double xa2 = in.nextDouble();
			double ya2 = in.nextDouble();
			double xb1 = in.nextDouble();
			double yb1 = in.nextDouble();
			double xb2 = in.nextDouble();
			double yb2 = in.nextDouble();
			String result = "NO";
			if (xa1 <= xb2 && xa2 >= xb1 && ya1 <= yb2 && ya2 >= yb1)
				result = "YES";
			System.out.println(result);
		}
	}
}

Measured memory_bytes: 20980
// Date: 2020-01-23

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> pii;
#define FIO ios::sync_with_stdio(false);cin.tie(0)
#define rep(i, a, b) for(int i = int(a); i <= int(b); ++i)
#define per(i, b, a) for(int i = int(b); i >= int(a); --i)
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define mem(x, y) memset(x, y, sizeof(x))
#define all(x) (x).begin(),(x).end()
#define SZ(x) x.size()
#define mk make_pair
#define pb push_back
#define fi first
#define se second
const LL INF = 1e18;
const LL mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 10;
LL qpow(LL x, LL y, LL MOD) {LL a=1; while(y){ if(y&1) a=a*x%MOD; x=x*x%MOD; y>>=1; } return a;}
LL inv(LL x) { return qpow(x, mod-2, mod); }

int n;
int x[N];
LL pre[N];

int main() {
	FIO;
	cin >> n;
	rep(i, 1, n) cin >> x[i];
	pre[1] = 1;
	rep(i, 2, n) pre[i] = (pre[i-1] + inv(i)) % mod;
	LL ans = 0;
	rep(i, 1, n-1) {
		ans += 1LL*(x[i+1]-x[i])*pre[i];
		ans %= mod;
	}
	rep(i, 1, n-1) ans = ans * i % mod;
	cout << ans;

	return 0;
}

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

int main(){
    long long N;
    cin >> N;
    long long val = 1;
    for(int i=1; i<=N; i++){
        val = (val*i)%(1000000000+7);
    }
    cout << val << endl;
    return 0;
}

Measured memory_bytes: 3532
#include <stdio.h>
#define S_MAX 4000

char str[S_MAX + 1],kis[S_MAX + 1];

int dp[S_MAX][S_MAX];

void solve(void){
	const sl = strlen(str), tl = strlen(kis);
	int a = 0;
	int i,j;
	memset(dp,0,sizeof dp);
	for(i=0;i<sl;i++){
		for(j=0;j<tl;j++){
			if(str[i] != kis[j]){
				dp[i][j] = 0;
			}
			else if(!i || !j){
				dp[i][j] = 1;
			}
			else{
				dp[i][j] = dp[i-1][j-1] + 1;
			}
			if(a < dp[i][j])a = dp[i][j];
		}
	}
	printf("%d\n", a);
	return;
}

int main(void){
	while(scanf("%s%s",str,kis) != EOF)solve();
	return 0;
}

Measured memory_bytes: 63060
#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/STACK: 2000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>

#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#define elif else if
#define lli long long int
#define ld long double
#define vec vector
#define forn(a) for(lli a=0; a<n; a++)
#define all(x) x.begin(), x.end()
#define presicion(x) cout<<fixed<<setprecision(x)
#define deb(x) cerr<<#x<<" = "<<x<<endl
#define PI 3.14159265358979323
#define sen(ang) sin((ang)*PI/180)
//cout<<flush;

using namespace std;

int main(){
    IOS;

    int n, a, b;
    cin>>n>>a>>b;

    int maximo = min(n, min(a, b));
    int minimo = (a+b)>=n ? (a+b)-n : 0;
    cout<<maximo<<" "<<minimo<<endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(int)(n); i++)

using namespace std;
typedef long long LL;
typedef pair<int,int> P;

int main(){
	LL N, M;
	cin >> N >> M;
	vector<LL> p;
	for(LL i=1; i*i<=M; i++){
		if(M%i==0){
			p.emplace_back(i);
			p.emplace_back(M/i);
		}
	}
	LL ans=1;
	rep(i,p.size()){
		if(p[i]*N<=M) ans=max(ans,p[i]);
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
# 2019-11-13 08:30:54(JST)
import sys
import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 

def main():
    n, m = [int(x) for x in sys.stdin.readline().split()]
    a = [int(x) for x in sys.stdin.readline().split()]

    a = list(collections.Counter(a).items())

    for _ in range(m):
        b, c = [int(x) for x in sys.stdin.readline().split()]
        a.append((c,b))
    
    a.sort(reverse=True)
    
    total = 0
    count = 0
    for i in range(n+m): # max
        select = a[i]
        for j in range(select[1], 0, -1):
            if count + j > n:
                continue
            else:
                count += j
                total += select[0] * j
                break
        if count == n:
            break
    
    print(total)

if __name__ == "__main__":
    main()


Measured memory_bytes: 28088
module graph_mod
    implicit none
    type node
        integer(4),allocatable:: to(:)
        integer(4):: l
    end type
    
contains
    subroutine init(n)
        type(node):: n
        allocate(n%to(1))

        n%l = 0
    end subroutine


    subroutine regist(n,m)
        type(node):: n
        integer(4):: m

        if (n%l+1 > size(n%to)) call add_(n)
        n%l=n%l+1
        n%to(n%l) = m
    end subroutine


    subroutine add_(n)
        type(node):: n
        integer(4),allocatable:: tmp(:)
        integer(4):: l

        l = size(n%to)
        allocate(tmp(l))
        tmp(:) = n%to(:)
        deallocate(n%to)
        allocate(n%to(l*2))
        n%to(1:l) = tmp(:)
        deallocate(tmp)
    end subroutine
end module

program name
    use,intrinsic :: iso_fortran_env
    implicit none
    integer(int32):: n,m,i,a,b,ans
    integer(int32), allocatable:: s(:),r(:)

    read*, n,m
    allocate(s(n),r(n))
    r(:) = 0
    read*, s(:)

    do i=1,m
        read*, a,b
        r(a) = max(r(a),s(b))
        r(b) = max(r(b),s(a))
    end do

    ans=0
    do i=1,n
        if (s(i) > r(i)) ans=ans+1
    end do
    print'(i0)', ans
end program name

Measured memory_bytes: 3788
#include <bits/stdc++.h>
using LL = long long;
using namespace std;

const int M = 2e5 + 100;
const int mod = 1e9 + 7;

vector<int> e[M];
int n, sz[M], ans[M];
int fac[M], inv[M];

LL mul(LL a, LL b) {
	return a * b % mod;
}

void init() {
	fac[0] = 1;
	for (int i = 1; i <= n; i++) fac[i] = mul(fac[i - 1], i);
	inv[1] = 1;
	for (int i = 2; i <= n; i++) inv[i] = mul((mod - mod / i), inv[mod % i]);
}

void dfs(int u, int fa) {
	sz[u] = 1;
	for (int v : e[u]) {
		if (v != fa) {
			dfs(v, u);
			sz[u] += sz[v];
		}
	}
}

void reroot(int u, int fa) {
	ans[u] = mul(mul(ans[fa], sz[u]), inv[n - sz[u]]);
	for (int v : e[u]) {
		if (v != fa) {
			reroot(v, u);
		}
	}
}

int main() {
	cin >> n;
	init();
	for (int i = 0; i < n - 1; i++) {
		int u, v; cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1, 0);
	ans[1] = fac[n];
	for (int i = 1; i <= n; i++) ans[1] = mul(ans[1], inv[sz[i]]);
	for (int v : e[1]) reroot(v, 1);
	for (int i = 1; i <= n; i++) cout << ans[i] << "\n";
}

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

#define ll long long
using namespace std;
const int N = 1e6 + 5, mod = 998244353;
ll a[N];
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    ll k, n;
    cin >> k >> n;
    for(int i = 0 ; i < n ; i++) cin >> a[i];
    ll ans = 1e18;
    ll cur;
    for(int i = 0 ; i < n ; i++) {
        cur = a[(i + n - 1) % n] - a[i];
        while (cur < 0) cur += k;
        ans = min(ans, cur);
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 1792
#include<iostream>
#include<string>
#include<math.h>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
#define N (1000000000+7)

int main(void) {
	int n, ma = 0, sum = 0, a;
	cin >> n;
	for (ll i = 0;i < n;i++) {
		cin >> a;
		ma = max(ma, a);
		sum += a;
	}
	cout << sum - ma + ma / 2 << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
	long long n,ans=10000000;
	string str;
	cin >> n;
	cin >> str;
	vector<long long> e(n),w(n);
	e[n-1] = 0;
	w[0] = 0;
	if(str[n-1]=='E')	e[n-1]++;
	if(str[0]=='W')	w[0]++;
	for(long long i=1;i<n-1;i++){
		if(str[i]=='W')	w[i]=w[i-1]+1;
		else	w[i]=w[i-1];
	}
	for(long long i=n-2;i>0;i--){
		if(str[i]=='E') e[i] = e[i+1]+1;
		else	e[i] = e[i+1];
	}
	ans = min(w[n-2],e[1]);
	for(long long i=1;i<n-1;i++){
			ans = min(ans,e[i+1]+w[i-1]);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 5380
s = input()
t = input()
if len(s) < len(t):
    print('UNRESTORABLE')
    exit()

for i in range(len(s)-len(t)+1)[::-1]:
    # print(s[i])
    for j in range(len(t)):
        if s[i+j] == '?':
            continue
        if s[i+j] != t[j]:
            break
    else:
        ans = s[:i] + t + s[i+len(t):]
        print(ans.replace('?', 'a'))
        break
else:
    print('UNRESTORABLE')


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

int main() {
  int a;
  string t;
  string u;
  cin >> a;
  for (int i = 0; i < a; i++)
  {
    cin >> t;
    if (t == "Y")
    {
      u = "Four";
      break; 
    }
    u = "Three";
  }
  cout << u << endl ;
}


Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
#define pie 3.141592653589793238462643383279
#define int long long
#define mod 1000000007
#define INF LLONG_MAX/5
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define S second
#define F first
#define f(i,n) for(int i=0;i<n;i++)
int x[300][300];
signed main(){
	int a,b,c;
	cin>>a>>b>>c;
	f(i,a){
		f(j,a){
			x[i][j]=INF;
		}
	}
	f(i,b){
		int y,z,d;
		cin>>y>>z>>d;
		x[y-1][z-1]=d;
		x[z-1][y-1]=d;
	}
	f(i,a){
		f(j,a){
			f(k,a){
				x[j][k]=min(x[j][k],x[j][i]+x[i][k]);
			}
		}
	}
	f(i,a){
		f(j,a){
			if(x[i][j]<=c)x[i][j]=1;
			else x[i][j]=INF;
		}
	}
	f(i,a){
		f(j,a){
			f(k,a){
				x[j][k]=min(x[j][k],x[j][i]+x[i][k]);
			}
		}
	}
	int q;
	cin>>q;
	f(i,q){
		int y,z;
		cin>>y>>z;
		if(x[y-1][z-1]!=INF)cout<<x[y-1][z-1]-1<<endl;
		else puts("-1");
	}
}


Measured memory_bytes: 1280
#include <iostream>
#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <complex>
#include <valarray>
#include <fstream>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <random>

#define _overload(a, b, c, d, ...) d
#define _rep1(X, A, Y) for (int (X) = (A);(X) <= (Y);++(X))
#define _rep2(X, Y) for (int (X) = 0;(X) < (Y);++(X))
#define rep(...) _overload(__VA_ARGS__, _rep1, _rep2)(__VA_ARGS__)
#define rrep(X,Y) for (int (X) = Y-1;(X) >= 0;--(X))
#define all(X) (X).begin(),(X).end()
#define _size(X) (int)((X).size())
#define mod(n, m) (((n)%(m)+(m))%m)
#define fi first
#define sc second
using namespace std;
typedef pair<int,int> Pii;
const int INFINT = 1 << 30;                          // 1.07x10^ 9
const double EPS = 1e-10;
const int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

const int MAX_N = 200000, MAX_Q = 200000;
int N, Q;
string s;
char t[MAX_Q], d[MAX_Q];

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

  cin >> N >> Q;
  cin >> s;
  rep(i, Q) cin >> t[i] >> d[i];

  int l = -1, r = N;
  for (int i = Q-1; i >= 0; --i) {
      int rl = l+1, lr = r-1;
      if (rl < N && s[rl] == t[i] && d[i] == 'L') {
           ++l;
      }
      if (lr >= 0 && s[lr] == t[i] && d[i] == 'R') {
          --r;
      }
      if (l >= 0 && s[l] == t[i] && d[i] == 'R')  {
          --l;
      }
      if (r < N && s[r] == t[i] && d[i] == 'L') {
          ++r;
      }
  }

  cout << N - (l+1) - (N-r) << endl;

  return 0;
}


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

#define     fast()              ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
#define     ll                  long long int
#define     test()              ll t; cin>>t; while(t--) 
#define     lp0(i,begin,end)    for(ll i=begin;i<end;i++)
#define     lp1(i,begin,end)    for(ll i=begin;i<=end;i++)
#define     rlp(i,begin,end)    for(ll i=end;i>=begin;i--)
#define     prec(n)             fixed<<setprecision(n)
#define     initial(a,i)        memset(a,i,sizeof(a))
#define     pb                  push_back
#define     PI                  3.1415926535897932384626433832795
#define     MOD                 1000000007
#define     F                   first
#define     S                   second
#define     all(a)              (a).begin(),(a).end()
#define     BPC(x)              __builtin_popcountll(x)
#define     gcd(a,b)            __gcd(a,b)

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

ll power(ll x,ll n)
{
    ll result = 1;
    while (n)
    {
        if (n & 1)
            result = result * x;
        n = n / 2;
        x = x * x;
    }
    return result;
}


// Solution Function
void solution(ll compte)
{
    // cout<<compte<<"\n";
    ll a,b,c;
    cin>>a>>b>>c;

    cout<<min((a+b),min((b+c),(c+a)));
}
    // Driver Function
int main()
{
    ll compte = 1;
    //test()
    //{
        solution(compte);
        compte++;
    //}
    return 0;
}


Measured memory_bytes: 3560
#include<stdio.h>
#include<iomanip>
#include<cstdio>
#include<vector>
#include<iostream>
#include<queue>
#include<deque>
#include<stack>
#include<set>
#include<map>
#include<utility>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<climits>
#include<string>
using namespace std;
#define lli long long int
#define f first
#define s second
#define sc(n) scanf("%d",&n);
#define scl(n) scanf("%lld",&n);
#define pr(n) printf("%d",n);
#define prl(n) printf("%lld",n);
#define nl printf("\n");
#define all(c) (c).begin(), (c).end()
#define sz(a) int((a).size())
#define FN(i,n) for (int i = 0; i < (int)(n); ++i)
#define FEN(i,n) for (int i = 1;i <= (int)(n); ++i)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define tr(c,i) for(typeof((c).begin() i = (c).begin(); i != (c).end(); i++))
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
			cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
			const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
void optimizeIO()
{
	        ios_base:: sync_with_stdio(false);
		        cin.tie(NULL);
}

int main()
{
	int n;
	cin >> n;
	int arr[111111];
	FN(i,n){
		cin >> arr[i+1];
	}

	int cost[111111];
	cost[1] = 0;
	cost[2] = abs(arr[2] - arr[1]);
	for(int i = 3; i <= n; i++)
	{
		cost[i] = min(cost[i-1] + abs(arr[i] - arr[i-1]), cost[i-2] + abs(arr[i] - arr[i-2]));
	}
	cout << cost[n];
}


Measured memory_bytes: 1024
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string>

using namespace std;

struct Node {
	int key;
	Node *right, *left, *parent;
};

Node *root, *NIL;

Node * treeMinimum(Node *x) {
	while (x->left != NIL) x = x->left;
	return x;
}

Node * find(Node *u, int k) {
	while (u != NIL && k != u->key) {
		if (k < u->key) u = u->left;
		else u = u->right;
	}
	return u;
}

Node * treeSuccessor(Node *x) {
	if (x->right != NIL) return treeMinimum(x->right);
	Node *y = x->parent;
	while (y != NIL && x == y->right) {
		x = y;
		y = y->parent;
	}
	return y;
}

void treeDelete(Node *z) {
	Node *y;
	Node *x;

	if (z->left == NIL || z->right == NIL) y = z;
	else y = treeSuccessor(z);

	if (y->left != NIL) {
		x = y->left;
	}
	else {
		x = y->right;
	}

	if (x != NIL) {
		x->parent = y->parent;
	}

	if (y->parent == NIL) {
		root = x;
	}
	else {
		if (y == y->parent->left) {
			y->parent->left = x;
		}
		else {
			y->parent->right = x;
		}
	}

	if (y != z) {
		z->key = y->key;
	}

	free(y);
}

void insert(int k) {
	Node *x = root;
	Node *y = NIL;
	Node *z;

	z = (Node *)malloc(sizeof(Node));
	z->key = k;
	z->left = NIL;
	z->right = NIL;

	while (x != NIL) {
		y = x;
		if (z->key < x->key)
			x = x->left;
		else
			x = x->right;
	}
	z->parent = y;
	if (y == NIL)
		root = z;
	else {
		if (z->key < y->key)
			y->left = z;
		else
			y->right = z;
	}
}

void inorder(Node *u) {
	if (u == NIL) return;
	inorder(u->left);
	printf(" %d", u->key);
	inorder(u->right);
}

void preorder(Node *u) {
	if (u == NIL) return;
	printf(" %d", u->key);
	preorder(u->left);
	preorder(u->right);
}


int main() {
	int n, i, x;
	string com;

	scanf("%d", &n);

	for (i = 0; i < n; i++) {
		cin >> com;
		if (com[0] == 'f') {
			scanf("%d", &x);
			Node *t = find(root, x);
			if (t != NIL) printf("yes\n");
			else printf("no\n");
		}
		else if (com == "insert") {
			scanf("%d", &x);
			insert(x);
		}
		else if (com == "print") {
			inorder(root);
			printf("\n");
			preorder(root);
			printf("\n");
		}
		else if (com == "delete") {
			scanf("%d", &x);
			treeDelete(find(root, x));
		}
	}

	return 0;
}


Measured memory_bytes: 22016
# -*- coding: utf-8 -*-
import math
x = int(input())

def is_prime(n):
    if n == 1:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return True
    return False


while is_prime(x):
    x += 1

print(x)


Measured memory_bytes: 9408
#include<algorithm>
#include<iostream>
#include<string>
#include<map>
using namespace std;

string s, s_;
map<char, char> to;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> s;
	s_ = s;
	reverse(s.begin(), s.end());
	to['b'] = 'd', to['d'] = 'b', to['p'] = 'q', to['q'] = 'p';
	for(auto &c : s) c = to[c];
	cout << (s == s_? "Yes": "No") << '\n';
	return 0;
}


Measured memory_bytes: 512
using System;

class C
{
	static void Main()
	{
		var h = Array.ConvertAll(Console.ReadLine().Split(), long.Parse);
		var r = 1;
		while (2 * h[0] <= h[1])
		{
			r++;
			h[0] *= 2;
		}
		Console.WriteLine(r);
	}
}


Measured memory_bytes: 27468
#include <bits/stdc++.h>
#define L long long
using namespace std;
int main()
{
	int n,m,x;
	scanf("%d%d", &n,&m);
	priority_queue<int>q;
	L sum = 0;
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &x);
		sum += x;
		q.push(x);
	}
	while (m)
	{
		L top = q.top();
		q.pop();
		sum -= top;
		int p = top / 2;
		sum += p;
		q.push(p);
		m--;
	}
	printf("%lld", sum);
	return 0;
}


Measured memory_bytes: 892
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  int ans = 32;
  cin >> N;
  for (int i = 0;i < N;i++){
    int A;
    int warikire = 0;
    cin >> A;
    while (A%2 == 0){
      A/=2;
      warikire++;
    }
    ans=min(ans,warikire);
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

"""
N rooms
M paths

0 room is start
"""
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

N, M = LI()
AB = []
for i in range(M):
    a,b = LI()
    a -= 1
    b -= 1
    AB.append((a,b))

paths = {}
for i in range(N):
    paths[i] = []
for a, b in AB:
    paths[a].append(b)
    paths[b].append(a)

uf = UnionFind(N)
for a,b in AB:
    uf.Unite(a,b)

ans = True
for i in range(N):
    if not uf.isSameGroup(0, i):
        ans = False

if ans == False:
    print("No")
    sys.exit()

q = collections.deque()

# node No, parent No
q.append((0, -1))

anss = [0 for i in range(N)]
rooms = [0 for i in range(N)]
rooms[0] = 1
while len(q) > 0:
    node, p = q.popleft()

    for path in paths[node]:
        if path == p:
            continue
        if rooms[path]: # すでに探索済み
            continue
        q.append((path, node))
        rooms[path] = 1
        anss[path] = node
print("Yes")
for ans in anss[1:]:
    print(ans + 1)




Measured memory_bytes: 63860
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <cctype>
#include <vector>
using namespace std;
typedef long long lint;
#define cout cerr
#define ni (next_num<int>())
template<class T>inline T next_num(){
	T i=0;char c;
	while(!isdigit(c=getchar())&&c!='-');
	bool flag=c=='-';
	flag?c=getchar():0;
	while(i=i*10-'0'+c,isdigit(c=getchar()));
	return flag?-i:i;
}
template<class T1,class T2>inline void apmax(T1 &a,const T2 &b){if(a<b)a=b;}
template<class T1,class T2>inline void apmin(T1 &a,const T2 &b){if(b<a)a=b;}
const int N=100,O=1000000007;
const lint L=1000000000000000000ll;
lint fib[N];
inline int gstep(lint x,lint y){
	if(x>y){
		swap(x,y);
	}
	int ans=0;
	for(int &i=ans;fib[i]<=x&&fib[i+1]<=y;i++);
	return max(ans-1,1);
}
struct pii{
	lint a,b;
};
vector<pii>vec[N];
inline void Main(){
	lint x=next_num<lint>(),y=next_num<lint>();
	int step=gstep(x,y);
	printf("%d ",step);
	if(step==1){
		printf("%lld\n",x%O*(y%O)%O);
		return;
	}
	lint ans=0;
	for(int i=0,ti=vec[step-1].size();i<ti;i++){
		lint a=vec[step-1][i].a,b=vec[step-1][i].b;
		assert(a<b);
		if(b<=x){
			ans+=max((y-a)/b,0ll)%O;
		}
		if(b<=y){
			ans+=max((x-a)/b,0ll)%O;
		}
	}
	printf("%lld\n",ans%O);
}
int main(){
	fib[0]=1,fib[1]=1;
	int fibcnt;
	for(int &i=fibcnt=1;fib[i]<=L;i++){
		fib[i+1]=fib[i]+fib[i-1];
	}
	vec[0].push_back((pii){1,1});
	for(int i=0;i<fibcnt;i++){
		for(int j=0,tj=vec[i].size();j<tj;j++){
			lint x=vec[i][j].a,y=vec[i][j].b;
			assert(x<=y);
			while(x+=y,x<fib[i+3]+fib[i]){
				assert(y>=fib[i+1]&&x>=fib[i+2]);
				assert(y<fib[i+2]||x<fib[i+3]);
				vec[i+1].push_back((pii){y,x});
			}
		}
	}
	for(int tot=ni;tot--;){
		Main();
	}
	return 0;
}

Measured memory_bytes: 4096
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  while(n!=0){
    int a,b,c;
    int mx=0,mn=0;
    for(int i=0;i<n;i++){
      cin>>a>>b>>c;
      mx=max(mx,c+b);
      if(mx==c+b){
	mn=a;
      }
    }
    cout<<mn<<' '<<mx<<endl;
    cin>>n;
  }
  return 0;
}



Measured memory_bytes: 2996
#include <bits/stdc++.h>
#include <limits.h>
#include <algorithm>  
#include <numeric>
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define endl '\n'
using ll = long long;
 
const int precision = 3;
const int modulo =  1000000007; // 10^9 + 7
const ll lmodulo =  1000000007; // 10^9 + 7
 
const double EPS = 1e-9;
const ll inf = 1e18;


void solve () {
	int n, m; cin >> n >> m;

	vector<vector<char>> grid(n, vector<char>(m));
	for (auto &r : grid) {
		for (auto &c : r) {
			cin >> c;
		}
	}

	vector<vector<ll>> dp(n , vector<ll>(m, 0));

	dp[0][0] = 1;
	for (auto r = 0; r < n; ++r) {
		for (auto c = 0; c < m; ++c) {
			if (r == 0 and c == 0) continue;
			if (grid[r][c] == '#') continue;
			dp[r][c] = r - 1 >= 0 ? dp[r - 1][c] : 0;
			dp[r][c] += c - 1 >= 0 ? dp[r][c - 1] : 0;
			dp[r][c] %= lmodulo;
		}
	}

	cout << dp[n - 1][m - 1];
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  cout.precision(precision);
  cout.setf(ios_base::fixed);
  solve();
  return 0;
}


Measured memory_bytes: 9088
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
#define all(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long inf = numeric_limits<long long>::max();
int main()
{
  int n, m, t, total;
  m = 0;
  t = 0;
  total = 0;
  cin >> n;
  rep(i, n) {
    t = 0;
    cin >> t;
    if (t > m) {
      m = t;
    }
    total += t;
  }
  cout << total - (m / 2) << endl;
  return 0;
}

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

const ll INF = 1e9;

matrix prod(const matrix& a, const matrix& b){
	int n = a.size();
	matrix res(n, vector<ll>(n, -INF));
	for(int i = 0;i < n;i++){
		for(int j = 0;j < n;j++){
			for(int k = 0;k < n;k++){
				res[i][k] = max(res[i][k], a[i][j] + b[j][k]);
			}
		}
	}
	return res;
}

matrix power(matrix a, int x){
	int n = a.size();
	matrix res(n, vector<ll>(n, -INF));
	for(int i = 0;i < n;i++) res[i][i] = 0;
	while(x){
		if(x & 1) res = prod(a, res);
		a = prod(a, a);
		x >>= 1;
	}
	return res;
}

int main() {
	int V, E, K;
	cin >> V >> E >> K;
	matrix G(V, vector<ll>(V, -INF));
	for(int i = 0;i < V;i++) G[i][i] = 0;
	for(int i = 0;i < E;i++){
		int u, v;
		ll c;
		cin >> u >> v >> c;
		G[u][v] = max(G[u][v], c);
	}
	int lb = 0, ub = K + 1;
	while(ub - lb > 1){
		int m = (lb + ub) >> 1;
		auto v = power(G, m);
		ll ma = 0;
		for(int i = 0;i < V;i++) ma = max(ma, *max_element(v[i].begin(), v[i].end()));
		if(ma >= K){
			ub = m;
		}
		else{
			lb = m;
		}
	}
	if(ub == K + 1){
		cout << -1 << endl;
		return 0;
	}
	cout << ub << endl;
	if(ub > 100) return 0;
	vector<vector<ll>> dp(ub + 1, vector<ll>(V, -INF));
	for(int i = 0;i < V;i++) dp[0][i] = 0;
	for(int x = 0;x < ub;x++){
		for(int i = 0;i < V;i++){
			for(int j = 0;j < V;j++){
				dp[x + 1][j] = max(dp[x + 1][j], dp[x][i] + G[i][j]);
			}
		}
	}
	int pos = 0;
	for(int i = 0;i < V;i++){
		if(dp[ub][i] > dp[ub][pos]) pos = i;
	}
	vector<int> res;
	res.push_back(pos);
	for(int i = ub;i > 0;i--){
		for(int to = 0;to < V;to++){
			if(dp[i - 1][to] + G[to][pos] == dp[i][pos]){
				res.push_back(to);
				pos = to;
				break;
			}
		}
	}
	assert((int)res.size() == ub + 1);
	reverse(res.begin(), res.end());
	for(int i = 0;i <= ub;i++){
		cout << res[i] << " \n"[i == ub];
	}
}




Measured memory_bytes: 3704
#include <cstdio>
#include <cstring>
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
int main()
{
    int point, runner[4], out, n;
    char event[16];
    scanf("%d", &n);
    point = out = 0;
    rep(i, 4) runner[i] = 0;
    while (true) {
        scanf("%s", event);
        runner[0] = 1;
        if (!strcmp(event, "HIT")) {
            if (runner[3]) point++;
            rep(i, 3) runner[3-i] = runner[2-i];
        }
        else if (!strcmp(event, "OUT")) {
            out++;
            if (out == 3) {
                printf("%d\n", point);
                n--;
                if (n == 0) break;
                point = out = 0;
                memset(runner, 0, sizeof(runner));
            }
        }
        else {
            rep(i, 4) if (runner[i]) point++;
            memset(runner, 0, sizeof(runner));
        }
    }
    return 0;
}

Measured memory_bytes: 0
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#define REP(i, m, n) for(int i=int(m);i<int(n);i++)
#define EACH(i, c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s, e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

//#define LOCAL 1
#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR
#endif


//改造
typedef long long int ll;
using namespace std;


//ここから編集する


int main() {
    int N;
    cin >> N;
    int minA = (1 << 30),minB = (1 << 30);
    REP(i,0,N){
        int A,B;
        cin >> A >> B;
        if(minB > B){
            minB = B;
            minA = A;
        }
    }
    cout << minB + minA << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <limits>
#include <chrono>
using namespace std;
 
typedef long long ll;
typedef pair<int, ll> Pl;

ll dist[100005];
vector<Pl> graph[100005];

struct Timer{
    chrono::high_resolution_clock::time_point st;

    Timer() { reset(); }

    void reset(){
        st = chrono::high_resolution_clock::now();
    }

    chrono::milliseconds::rep elapsed(){
        auto ed = chrono::high_resolution_clock::now();
        return chrono::duration_cast<chrono::milliseconds>(ed - st).count();
    }
};

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

    Timer t;
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; ++i){
        int l, r;
        ll c;
        cin >> l >> r >> c;
        --l, --r;
        graph[l].push_back(Pl(r, c));
    }
    for(int i = 0; i < n-1; ++i){
        graph[i+1].push_back(Pl(i, 0));
    }
    
    fill(dist, dist+n, (ll)1e+17);
    dist[0] = 0;
    priority_queue<Pl, vector<Pl>, greater<Pl>> que;
    que.push(Pl(0, 0));
    while(!que.empty() && t.elapsed() < 1900){
        Pl p = que.top();
        que.pop();
        ll d = p.first;
        int u = p.second;
        if(dist[u] < d)     continue;
        for(int i = 0; i < (int)graph[u].size(); ++i){
            int v = graph[u][i].first;
            ll cost = graph[u][i].second;
            if(dist[v] > dist[u] + cost){
                dist[v] = dist[u] + cost;
                que.push(Pl(dist[v], v));
            }
        }
    }
    if(dist[n-1] == (ll)1e+17)  dist[n-1] = -1;
    cout << dist[n-1] << "\n";
}

Measured memory_bytes: 12532
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef pair<int, int> P;
typedef long long ll;
int main(){
    int a,b;
    cin >> a >> b;
    string s;
    cin >> s;
    rep(i,s.length()){
        if(i==a){
            if(s[i]!='-')
            {
                cout << "No" << endl;
                return 0;
            }
        }
        else{
            if(s[i]=='-'){
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256