akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <string>
#include <sstream>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <stack>
#include <cstdio>
#include <climits>
#include <tuple>
#include <ctime>
#include <cstring>
#include <numeric>
#define FOR(i,a,n) for (int i = a; i < n; i++)
#define IFOR(i,n,a) for (int i = n; i >= a; i--)
#define mp make_pair
#define full(a) a.begin(), a.end()
#define sz(x) ((int)(x).size())
#define pii pair<int, int>
#define trav(a,x) for (auto& a : x)
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
using namespace std;
const ll mod = 1e9 + 7;



int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n, x, t; cin >> n >> x >> t;
    if (n % x == 0)
    {
        cout << n / x * t;
    }
    else
    {
        cout << (n / x + 1) * t;
    }
    return 0;
}





Measured memory_bytes: 3196
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define pa pair<int,int>
const int Maxn=2010;
const int inf=2147483647;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*f;
}
int n,k,q,a[Maxn],b[Maxn],c[Maxn],lc,d[Maxn],ld,ans=inf;bool mark[Maxn];
int main()
{
	n=read(),k=read(),q=read();
	for(int i=1;i<=n;i++)a[i]=b[i]=read();
	sort(b+1,b+1+n);int m=unique(b+1,b+1+n)-b-1;
	mark[0]=mark[n+1]=true;
	for(int i=1;i<=m;i++)
	{
		int lst=0;ld=0;
		for(int j=1;j<=n+1;j++)
		if(mark[j])
		{
			if(j-lst-1>=k)
			{
				lc=0;
				for(int l=lst+1;l<j;l++)c[++lc]=a[l];
				sort(c+1,c+1+lc);
				for(int l=1;l<=lc-k+1;l++)d[++ld]=c[l];
			}
			lst=j;
		}
		if(ld<q)break;
		sort(d+1,d+1+ld);
		ans=min(ans,d[q]-d[1]);
		for(int j=1;j<=n;j++)if(a[j]==b[i])mark[j]=true;
	}
	printf("%d",ans);
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws NumberFormatException,
			IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(
				System.in));
		StringBuilder builder = new StringBuilder();
		StringTokenizer tokenizer;
		int n = Integer.parseInt(reader.readLine());
		for (int i = 0; i < n; i++) {
			tokenizer = new StringTokenizer(reader.readLine());
			double x1 = Double.parseDouble(tokenizer.nextToken());
			double y1 = Double.parseDouble(tokenizer.nextToken());
			double x2 = Double.parseDouble(tokenizer.nextToken());
			double y2 = Double.parseDouble(tokenizer.nextToken());
			double x3 = Double.parseDouble(tokenizer.nextToken());
			double y3 = Double.parseDouble(tokenizer.nextToken());

			double A = x1 * x1 - x2 * x2 + y1 * y1 - y2 * y2;
			double B = Math.pow(x1, 2) - Math.pow(x3, 2) + Math.pow(y1, 2)
					- Math.pow(y3, 2);
			double C = (y1 - y3) * (x1 - x2) - (y1 - y2) * (x1 - x3);
			double b = (B * (x1 - x2) - A * (x1 - x3)) / (2 * C);
			double a = (B * (y1 - y2) - A * (y1 - y3)) / (2 * (-C));
			double r = Math.sqrt((x1 - a) * (x1 - a) + (y1 - b) * (y1 - b));

			builder.append(String.format("%.3f %.3f %.3f\n", a, b, r));
		}
		System.out.print(builder);

	}

}

Measured memory_bytes: 17008
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Console;
using static System.Math;
using static AtCoderTemplate.MyLibrary;

namespace AtCoderTemplate
{
    class Program
    {
        static void Main (string[] args)
        {
            string[] str = Console.ReadLine ().Split (' ');
            int N = int.Parse (str[0]);
            int M = int.Parse (str[1]);

            int[] A = new int[N];
            double sum = 0;
            int count = 0;

            str = Console.ReadLine ().Split (' ');
            for (int i = 0; i < N; i++)
            {
                A[i] = int.Parse (str[i]);
                sum += A[i];
            }

            for (int i = 0; i < N; i++)
            {
                if (A[i] >= sum / (4 * M)) count++;
            }

            if (count >= M) { Console.WriteLine ("Yes"); }
            else { Console.WriteLine ("No"); }
        }
    }

    class MyLibrary
    {

        // 自作の関数
        public static int MyFunction (int n)
        {
            return 0;
        }
    }
}

Measured memory_bytes: 27520
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;

int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	int n, m; cin >> n >> m;
	vector<pi> v;
	rep(i, n){
		int a; cin >> a;
		v.emplace_back(a, 1);
	}
	rep(i, m){
		int b, c; cin >> b >> c;
		v.emplace_back(c, b);
	}
	sort(all(v)); reverse(all(v));
	ll ans = 0;
	for(pi i : v){
		int k = min(n, i.second);
		ans += k * (ll)i.first;
		n -= k;
	}
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 2420
import fractions

A,B,C,D = (int(a) for a in input().split())

U = B - A  + 1
c = (B // C) + (-A // C) + 1
d = (B // D) + (-A // D) + 1
x = C * D // fractions.gcd(C , D)
e = (B // x) + (-A // x) + 1
print(U - c - d + e)



Measured memory_bytes: 5048
#include <bits/stdc++.h>
#include <string>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001
typedef pair<int,int> P;
#define mod 1000000007

int main(){
    int a,b;
    cin >> a >> b;
    if(a*b%2==0) cout << "Even" <<endl;
    else cout << "Odd" << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <math.h> 
#include <string> 
#include <algorithm>
using namespace std;

int main() {

	char b; cin >> b;

	char res = 'A'; 

	res = (b == 'A') ? 'T' : res;
	res = (b == 'G') ? 'C' : res;
	res = (b == 'C') ? 'G' : res;

	cout << res << endl;

}

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

int main() {
  int n,m;cin>>n>>m;
  int s=0,a;
  rep(i,m) {
    cin>>a;
    s+=a;
  }
  cout<<max(-1, n-s);
}


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

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MAX=2005;
const ll INF=0x3f3f3f3f;
const ll MOD=998244353;
int n,par[MAX],depth[MAX],m,cnt[MAX][MAX],fcnt[MAX][MAX],chk_ans2[MAX],ans;
vector<int> conn[MAX],walk[MAX],lotus[MAX][MAX];
vector<pii> ans2;
queue<pii> now_edge;
void build(int px,int x,int d){
    depth[x]=d; par[x]=px;
    for(int i=0;i<conn[x].size();i++) if(conn[x][i]!=px) build(x,conn[x][i],d+1);
}
void seq_push(int idx,int pt,int fin,int mode){
    if(pt!=fin&&mode) walk[idx].push_back(pt);
    if(pt!=fin) seq_push(idx,par[pt],fin,mode);
    if(!mode) walk[idx].push_back(pt);
}
int process(){
    if(now_edge.size()==0){
        for(int i=0;i<m;i++) if(chk_ans2[i]==0){
            chk_ans2[i]=1;
            for(int j=0;j<walk[i].size()-1;j++) {
                int t1=walk[i][j],t2=walk[i][j+1];
                fcnt[t1][t2]++;
                if(cnt[t1][t2]-fcnt[t1][t2]==1&&fcnt[t2][t1]==0) now_edge.push(make_pair(t2,t1));
            }
            return 1;
        }
        return 0;
    }
    pii tmp=now_edge.front();
    int a=tmp.first,b=tmp.second,i,rev=0;
    now_edge.pop();
    if(fcnt[a][b]==0){
        fcnt[a][b]++;
        for(int j=0;j<lotus[a][b].size();j++){
            if(chk_ans2[lotus[a][b][j]]==0) i=lotus[a][b][j];
        }
        chk_ans2[i]=1;
        for(int j=0;j<walk[i].size()-1;j++){
            if(a==walk[i][j+1]&&b==walk[i][j]) rev=1;
        }
        if(rev) swap(ans2[i].first,ans2[i].second);
        for(int j=0;j<walk[i].size()-1;j++) {
            int t1=walk[i][j],t2=walk[i][j+1];
            if(rev) swap(t1,t2);
            fcnt[t1][t2]++;
            if(cnt[t1][t2]-fcnt[t1][t2]==1&&fcnt[t2][t1]==0) now_edge.push(make_pair(t2,t1));
        }
    }
    return 1;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n-1;i++){
        int t1,t2;
        scanf("%d%d",&t1,&t2);
        conn[t1].push_back(t2);
        conn[t2].push_back(t1);
    }
    build(1,1,0);
    for(int i=0;i<m;i++){
        int a,b,t1,t2;
        scanf("%d%d",&a,&b);
        t1=a,t2=b;
        if(depth[t1]>depth[t2]) swap(t1,t2);
        while(depth[t2]!=depth[t1]) {t2=par[t2];}
        while(t1!=t2) {t1=par[t1],t2=par[t2];}
        seq_push(i,a,t1,1);
        seq_push(i,b,t1,0);
        ans2.push_back(make_pair(a,b));
        for(int j=0;j<walk[i].size()-1;j++) {
            lotus[walk[i][j]][walk[i][j+1]].push_back(i);
            lotus[walk[i][j+1]][walk[i][j]].push_back(i);
        }
    }
    for(int i=0;i<m;i++) for(int j=0;j<walk[i].size()-1;j++) cnt[walk[i][j]][walk[i][j+1]]++,cnt[walk[i][j+1]][walk[i][j]]++;
    while(process());
    for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) ans+=min(cnt[i][j],2);//printf("%d %d %d\n",i,j,cnt[i][j]);
    printf("%d\n",ans);
    for(int i=0;i<m;i++) printf("%d %d\n",ans2[i].first,ans2[i].second);
}


Measured memory_bytes: 145280
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <functional>
#define SIZE 100005

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

ll left[SIZE],right[SIZE];
ll sum[SIZE];
ll A[SIZE];

ll gt(int s,int t)
{
	return sum[t]-(s==0?0:sum[s-1]);
}
int main()
{
	int n,k;
	scanf("%d %d",&n,&k);
	for(int i=0;i<n;i++)
	{
		scanf("%lld",&A[i]);
		sum[i]=A[i];
		if(i>0) sum[i]+=sum[i-1];
	}
	ll now=0;
	for(int i=0;i<n;i++)
	{
		left[i]=now;
		now+=max(0LL,A[i]);
	}
	now=0;
	for(int i=n-1;i>=0;i--)
	{
		right[i]=now;
		now+=max(0LL,A[i]);
	}
	ll ret=0;
	for(int i=0;i+k<=n;i++)
	{
		int s=i,t=i+k-1;
		ll now=max(0LL,gt(s,t));
		now+=left[s];
		now+=right[t];
		ret=max(ret,now);
	}
	printf("%lld\n",ret);
	return 0;
}


Measured memory_bytes: 3328
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

void main()
{
    auto N = readln.chomp.to!int;
    auto AS = readln.split.to!(double[]);
    double dp = 0;
    foreach (i; 0..N) {
        dp += 1.0 / AS[i];
    }
    writefln("%.10f", 1.0 / dp);
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void){
  long a,b,S;
  int k,n;
  while(scanf("%ld %ld",&a,&b)!=EOF){
    n=0;
    S = a + b;
    for(k=1;k<=7;k++){
      S/=10;
      n++;
      if(S==0) break;
    }
    printf("%d\n",n);
  }
  return 0;
}

Measured memory_bytes: 600
program main

  implicit none

  integer    :: n
  integer,allocatable :: x(:)

  integer    :: i, j, mdmin, md

  read(*,*) n
  allocate( x(n) )
  read(*,*) x
  
  do i = 1, 100
    md = 0

    do j = 1, n
      md =  md + ( x(j) - i )**2
    end do

    if( i == 1 ) then
       mdmin = md
    else
      if( mdmin > md ) then
       mdmin = md
      end if
    end if

  end do
  print*, mdmin
  
  !call quicksort1( p, 1, int( n*(n-1) )+1 ) 
  !call quicksort1( p, 1, n*(n-1)/2 ) 

  !print*, p(k)

end program main

recursive subroutine quicksort1(a, first, last)
  implicit none
  integer(8),intent(inout)::a(*)
  integer,intent(in)::first,last
  !
  ! Original
  ! https://gist.github.com/t-nissie/479f0f16966925fa29ea
  !
  integer(8)::x,t
  integer::i,j

  x = a((first+last)/2)
  i = first
  j = last
  do
     do while (a(i) < x)
        i=i+1
     end do
     do while (x < a(j))
        j=j-1
     end do
     if (i >= j) exit
     t = a(i)
     a(i) = a(j)
     a(j) = t
     i=i+1
     j=j-1
  end do
  if (first < i-1) call quicksort1(a, first, i-1)
  if (j+1 < last)  call quicksort1(a, j+1, last)

  return
end subroutine quicksort1


Measured memory_bytes: 256
use strict;
use warnings;
use utf8;
use Data::Dumper;

use feature qw(say);

my $list = <STDIN>;
chomp $list;

my ($x, $n) = (split/ /, $list);

my $list2 = <STDIN>;
chomp $list2;
my $num_array = [split/ /, $list2];

my $candidate = [0..101];
my $sorted = [sort { abs($a - $x) <=> abs($b - $x) || $a <=> $b } @$candidate];

my $exist_mapping = +{map { $_ => 1 } @$num_array};
for my $num (@$sorted) {
    unless ($exist_mapping->{$num}) {
        say $num;
        exit 0;
    }
}

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

int main()
{
  cin>>N;
  vector<tuple<string, int, int>> v(N);
  for(int i=0; i<N; i++){
    string s;  int p;  int num = i+1;
    cin>>s>>p;
    v[i] = make_tuple(s, -p, num);
  }

  sort(v.begin(), v.end());

  for(int i=0; i<N; i++){
    int z;
    tie(ignore, ignore, z) = v[i];
    cout<<z<<endl;
  }
}


Measured memory_bytes: 256
# デバッグ用
GBN_DEBUG = False
def dprn(s, i):
    if GBN_DEBUG: print(", " + s + " = " + str(i), end = "")
def dprns(s):
    if GBN_DEBUG: print(", " + s, end = "")
def dprni(i):
    if GBN_DEBUG: print(i, end=" ")
def endl(): 
    if GBN_DEBUG: print('')
def puts(s): print(s)

#本体ここから

#S = input()
#N = int(input())
#S, T = input().split()
A, B = map(int, input().split())
#W = [input() for _ in range(N)]
#A = list(map(int, input().split()))

#GBN_DEBUG = True

s = A + B
d = A - B
p = A * B

ans = max(s, d)
ans = max(ans, p)

print(ans)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int N;
    cin >> N;
    bool a=false;
    for(int i=1;i<10;i++){
        for(int j=1;j<10;j++){
            if(i*j==N) a=true;
        }
    }    
    if(a)cout << "Yes" << endl;
    else cout << "No" << endl;

}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<numeric>
#include<algorithm>
#include<stdio.h>
using namespace std;
 
long long R[100000];
long long A[100000];
 
int gcd( int m, int n )
{
	if ( ( 0 == m ) || ( 0 == n ) )
		return 0;
	
 
	while( m != n )
	{
		if ( m > n ) m = m - n;
		else         n = n - m;
	}
	return m;
}
 
int main(){
    long long N, X; cin >> N >> X;
    for (int i = 0; i < N; i++){
        cin >> R[i];
    }
    for (int i = 0; i < N; i++){
        A[i] = R[i] - X;
    }
    for (int i = 0; i < N; i++){
        if (A[i] < 0){
            A[i] = -A[i];
        }
        if(A[i]==0){
            A[i] = 1000000;
        }
    }
 
 
    int ans;
    if (N == 1){
        ans = A[0];
    } 
    else if (N == 2)
    {
        ans = gcd(A[0], A[1]);
    }
    else{
        ans = A[0];
        for(int i = 0; i < N - 2; i++){
            ans = gcd(gcd(A[i], A[i+1]), ans);
        }
    }
    cout << ans << endl;
 
}

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    int ans = 0;
    rep(i,n) {
        int A;
        cin >> A, --A;
        a[i] = A;
    }
    for(int i = 0; i < n; ++i){
        if(a[a[i]]==i) ans++;
        
    }
    cout << (ans+1)/2 << endl;
    return 0;
}

Measured memory_bytes: 3732
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>

using namespace std;

#define MAX_V 10000
#define INF INT_MAX / 2

struct edge { int to, cost; };
typedef pair<int, int> P;

int V;
vector<edge> G[MAX_V];
int d[MAX_V];

void dijkstra(int s) {
	priority_queue<P, vector<P>, greater<P> > que;
	fill(d, d + V, INF);
	d[s] = 0;
	que.push(P(0, s));

	while (!que.empty()) {
		P p = que.top(); que.pop();
		int v = p.second;
		if (d[v] < p.first)
			continue;
		for (int i = 0; i < G[v].size(); i++) {
			edge e = G[v][i];
			if (d[e.to] > d[v] + e.cost) {
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to], e.to));
			}
		}
	}
}

int main() {
	int n;
	cin >> n;
	V = n;
	for (int i = 0; i < n; i++) {
		int u, k;
		cin >> u >> k;
		for (int j = 0; j < k; j++) {
			edge e;
			cin >> e.to >> e.cost;
			G[u].push_back(e);
		}
	}
	dijkstra(0);
	for (int i = 0; i < n; i++)
		cout << i << " " << d[i] << endl;

	return 0;
}

Measured memory_bytes: 6312
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define range(a) (a).begin(),(a).end()
#define print(A,x,n) rep(i,0,n){cout<<(i ? " ":"")<<A[i]x;}cout<<endl;
#define pprint(A,y,m,n) rep(j,0,m){print(A[j],y,n);}
const long mod=1e9+7;
const int siz=2e5;
const int inf=1e9;
int main(){
	char x,y; cin>>x>>y;
	if(x > y) cout<<">"<<endl;
    else if(x == y) cout<<"="<<endl;
    else cout<<"<"<<endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...)name
#define _rep(i,n)repi(i,0,n)
#define repi(i,a,b)for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x)x
#define rep(...)MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c)c.begin(),c.end()
#define write(x)cout<<(x)<<'\n'
using namespace std; typedef long long ll; template<class T>using vv = vector<vector<T>>;
template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
template<class T, class U>bool chmax(T& a, U&& b) { return a < b ? a = b, 1 : 0; }
template<class T, class U>bool chmin(T& a, U&& b) { return b < a ? a = b, 1 : 0; }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); }; }aaaa;

struct Combination {
    static ll mpow(ll x, ll n) { ll y = 1; for (; n > 0; n /= 2) { y = n % 2 ? y * x % MOD : y; x = x * x % MOD; } return y; }
    vector<ll> fact, ifact;
    Combination(int n) : fact(n + 1), ifact(n + 1) {
        fact[0] = 1; for (int i = 0; i < n; ++i) fact[i + 1] = fact[i] * (i + 1) % MOD;
        ifact[n] = mpow(fact[n], MOD - 2); for (int i = n; i > 0; --i) ifact[i - 1] = ifact[i] * i % MOD;
    }
    ll operator ()(int n, int k) { return k < 0 || k > n ? 0 : fact[n] * ifact[n - k] % MOD * ifact[k] % MOD; }
} Combi(2e5);

int main() {
    int H, W, N;
    cin >> H >> W >> N;
    vector<int> R(N + 2), C(N + 2);
    rep(i, 1, N + 1) {
        cin >> R[i] >> C[i];
        R[i]--;
        C[i]--;
    }
    R[N + 1] = H - 1;
    C[N + 1] = W - 1;

    vector<int> sorted(N + 2);
    iota(all(sorted), 0);
    sort(all(sorted), [&](int l, int r) { return R[l] + C[l] < R[r] + C[r]; });

    vv<ll> graph = vvec(N + 2, N + 2, 0LL);
    rep(i, N + 1) rep(j, N + 2) {
        if (R[sorted[i]] <= R[sorted[j]] && C[sorted[i]] <= C[sorted[j]]) {
            graph[i][j] = Combi(R[sorted[j]] - R[sorted[i]] + C[sorted[j]] - C[sorted[i]], R[sorted[j]] - R[sorted[i]]);
        }
    }

    vector<ll> dp(N + 2);
    rep(i, 1, N + 1) {
        dp[i] = graph[0][i];
        rep(j, 1, i) {
            dp[i] = (dp[i] - dp[j] * graph[j][i]) % MOD;
        }
        dp[i] = (dp[i] + MOD) % MOD;
    }

    ll ans = graph[0][N + 1];
    rep(i, 1, N + 1) ans = (ans - dp[i] * graph[i][N + 1]) % MOD;
    write((ans + MOD) % MOD);
}

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

int K[11], S[11][11], P[11];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        cin >> K[i];
        for (int j = 0; j < K[i]; j++) {
            cin >> S[i][j];
            S[i][j]--;
        }
    }
    for (int i = 0; i < M; i++) cin >> P[i];
    int ans = 0;
    for (int mask = 0; mask < 1 << N; mask++) {
        int sum = 0;
        for (int i = 0; i < M; i++) {
            int on_cnt = 0;
            for (int j = 0; j < K[i]; j++) {
                if ((mask >> S[i][j]) & 1) on_cnt++;
            }
            if (on_cnt % 2 == P[i]) sum++;
        }
        if (sum == M) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef struct city_data{
    string city_name;
    int point;
    int number;
}c_data_t;

bool city_dict(c_data_t prev, c_data_t next)
{
    if(prev.city_name < next.city_name){
        return true;
    }else if(prev.city_name == next.city_name){
        if(prev.point > next.point){
            return true;
        }
    }

    return false;
}

int main(void)
{
    int restaurants_count;
    vector<c_data_t> city_data;

    cin >> restaurants_count;

    for(int i = 0; i < restaurants_count; i++){
        string city;
        int point;
        cin >> city >> point;
        c_data_t city_datum = {city, point, i + 1};
        city_data.push_back(city_datum);
    }

    sort(city_data.begin(), city_data.end(), city_dict);

    for(int i = 0; i < restaurants_count; i++){
        cout << city_data[i].number << endl;
    }

    return 0;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
const ll mod = 1000000007;
const ll INF = 1000000099;
//cin.tie(0);
//ios::sync_with_stdio(false);


//添え字がでないならfalseにする
void eratosthenes(vector<bool> &v,int N){//vector(N+1,true)で初期化すること
    v.at(1)=false;
    for(int i=2;i < N+1;i++){
        if(v.at(i)==true){
            for(int j=2*i;j < N+1;j += i){//Nを宣言してなかった、注意
                v.at(j) = false;
            }
        }
    }
}//エラトステネスの篩 添え字が素数ならtrueのまま 素数でないならfalseに変える
//初期宣言はtrue

//判定が必要な数の最大値のサイズを持ち、要素が全てtrueのvectorを入力する

signed main(){
    vector<bool> f(55556,true);
    vector<vector<int>> v(5,vector<int>());
    int n;
    cin>>n;
    eratosthenes(f,55555);

    for(int i=1;i < 55556;i++)
    {
        if(f.at(i)){
            if(i%5==1)v.at(1).pb(i);
            else if(i%5==2)v.at(2).pb(i);
            else if(i%5==3)v.at(3).pb(i);
            else if(i%5==4)v.at(4).pb(i);
        }
    }
    int m;
    for(int i=1;i<5;i++){
        if(siz(v.at(i))>n-1){
            m=i;
        }
    }

    for (int i = 0; i < n; i++)
    {
        cout<<v.at(m).at(i)<<" ";
    }
    cout<<endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <unistd.h>
#define U 0
#define R 1
#define D 2
#define L 3

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

using namespace std;

int wall[5][5];
char buf[128];
void readH(int y){
//  read(0,buf,6);buf[4]=0;
  scanf("%s",buf);
  for (int i=0; i<4; i++){
    wall[i][y] |= (buf[i]=='1') << R;
    wall[i+1][y] |= (buf[i]=='1') << L;
  }
}
void readV(int y){
  scanf("%s",buf);
  for (int i=0; i<5; i++){
    wall[i][y] |= (buf[i]=='1') << D;
    wall[i][y+1] |= (buf[i]=='1') << U;
  }
}
int main(void){
  int x,y,dir;
  
  for (int i=0; i<4; i++){
    readH(i); readV(i);
  }
  readH(4);
  
/*  for (int y=0; y<=4; y++){
    for (int x=0; x<=4; x++){
      printf("%x ", wall[x][y]);
    }puts("");
  }
  */
//  for(x=y=(dir=R)^R;x+=dx[dir],y+=dy[dir],write(1,&(*buf="URDL"[dir]),1),x+y;){
  for(x=y=(dir=R)^R;x+=dx[dir],y+=dy[dir],putchar("URDL"[dir]),x+y;){
    for((dir+=3)&=~4;!(wall[x][y]&(1<<dir)); (dir+=1)&=~4){
    }
  }
puts("");
  return 0;
}


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

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

typedef long long LL;
typedef unsigned long UL;

using namespace std;

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

    int a, b;

    cin >> a >> b;

    cout << (a - 1) * (b - 1) << endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
using namespace std;
int n, x, ans;
int main(){
	scanf("%d", &n);
	while(n--){
		scanf("%d", &x);
		while(!(x & 1)){//用位运算节省时间
			ans++;
			x >>= 1;//还是位运算QWQ
		}
	}
	printf("%d\n", ans);//注意 AT 题要换行
	return 0;//完结撒花-v-
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;
long long int gcd(int long long p,int long long q)
{
    int rem;
    while(q>0)
    {
        rem=p%q;
        p=q;
        q=rem;
    }
    return p;
}

int main()
{
    long long int n,a[100000],i,b=0;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>a[i];
        b=gcd(b,a[i]);
    }
    cout<<b<<endl;


    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file 
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional> // for less 
#define pb push_back
#define For(i,s,e) for (ll i=(s); i<(e); i++)
#define Debug_array(a,n) for (ll i=(0); i<(n); i++) cout<<a[i]<<" "
#define Foe(i,s,e) for (ll i=(s); i<=(e); i++)
#define Fod(i,s,e) for (ll i=(s)-1; i>=(e); i--)
#define pii pair<ll,ll>
#define fi first
#define se second
#define endl "\n"
#define mp make_pair
#define big_prime 15486277
#define bigger_prime 179424697
#define biggest_prime 32416188691
//#define random_shuffle(indices.begin(), indices.end());
//std::random_device rd;
//std::mt19937 g(rd());
//std::shuffle(v.begin(), v.end(), g);
using namespace __gnu_pbds; 
using namespace std;
template <class T> ostream& operator << (ostream &os, const vector<T> &v) { for (T i : v) os << i << ' '; return os; }
template <class T> ostream& operator << (ostream &os, const set<T> &v) { for (T i : v) os << i << ' '; return os; }
template <class T, class S> ostream& operator << (ostream &os, const pair<T, S> &v) { os << v.first << ' ' << v.second; return os; }
// template <class T, class S> ostream& operator << (ostream &os, const unordered_map<T, S> &v) { for (auto i : v) os << '(' << i.first << "=>" << i.second << ')' << ' '; return os; }
 
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <class Arg1> void __f(const char* name, Arg1&& arg1) { cerr << name << " : " << arg1 << endl; }
    template <class Arg1, class... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args) {
        const char* sep = strchr(names + 1, ',');
        cerr.write(names, sep - names) << " : " << arg1 << "  ";
        __f(sep + 1, args...);
    }
#else
#define trace(...) 0
#define _CRT_SECURE_NO_WARNINGS
#endif // ifndef ONLINE_JUDGE


typedef long long ll;
typedef tree<ll, null_type, less<ll>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; 

#define Mod 1000000007
#define MAX 5002

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	ll n;cin>>n;
	if(n%2!=0){
		cout<<0<<endl;
		return 0;
	}else{
		n = n/2;
		ll ans = 0;
		ll x = 5;
		while(1){
			ans += (n/x);
			if(x>n/5) break;
			x = x*5;
		}
		cout<<ans<<endl;
	}































	
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(int i=0;i<N;++i)
typedef long long int LL;

int N, Ma, Mb;
std::vector<int>a, b, c;
std::vector<std::vector<std::vector<int>>>memo(41, std::vector<std::vector<int>>(412, std::vector<int>(412, -1)));

int dp(int n, int aa, int bb)
{
	if (aa > 0 && bb > 0 && aa*Mb / Ma == bb && bb*Ma / Mb == aa) return 0;
	if (n == N) return 114514;
	if (memo[n][aa][bb] != -1) return memo[n][aa][bb];
	int res1 = dp(n + 1, aa + a[n], bb + b[n]) + c[n];
	int res2 = dp(n + 1, aa, bb);
	return memo[n][aa][bb] = std::min(res1, res2);
}

int main()
{
	in >> N >> Ma >> Mb;
	a = std::vector<int>(N);
	b = std::vector<int>(N);
	c = std::vector<int>(N);
	//a.resize(N), b.resize(N), c.resize(N);
	rep(i, N) in >> a[i] >> b[i] >> c[i];
	out << (dp(0, 0, 0) >= 114514 ? -1 : dp(0, 0, 0)) << std::endl;
	return 0;
}

Measured memory_bytes: 28800
#include <math.h>
#include <bits/stdc++.h>
#include <deque>
#include <string>
#include <vector>
#include <algorithm>
#define ll long long int
#define l long double
#define pi 3.14159265358979323846
#define mod 1000000007
#define vali 1000000000000000000
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    l n,d,cnt=0;
    cin>>n>>d;
    for(int i=1;i<=n;i++)
    {
        l x,y;
        cin>>x>>y;
        if(x<0)
        x=x*-1;
        if(y<0)
        y*=-1;
        l ans=x*x+y*y;
        if(ans<=d*d)
        cnt++;
    }
    cout<<cnt<<endl;
}


Measured memory_bytes: 3816
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

ans=0
for i in range(len(A)):
    ans+=B[A[i]-1]
    if i>0:
        if A[i]==A[i-1]+1:
            ans+=C[A[i-1]-1]
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define T() long long t;cin>>t;for(long long i=1;i<=t;i++)
#define INF (int)MAX_INT
#define INFS (int)MIN_INT
#define mod 1000000007
#define FOR(a, b, n) for(int a = b; a < n; a++)
#define REP(a,c, b) for(int a = c; a < b; a++)
#define FORD(a, b, c) for(int a = b; a >= c; a--)
#define REPD(a, c,b) for(int a = b-1; a >= c; a--)
#ifdef HOHOHO
#define DEBUG(x) cerr << #x << " : " << x << '\n'
#define DEBUGV(x) cerr << #x << " : { "; REP(_it, x.size()) cerr << x[_it] << ' '; cerr << "}" << '\n'
#define DEBUGA(x, y) cerr << #x << " : { "; REP(_it, y) cerr << x[_it] << ' '; cerr << "}" << '\n'
#define PRINTF(...) fprintf(stderr,__VA_ARGS__)
#define CHECKPOINT cerr << "OK LINE #" << __LINE__ << '\n'
#else
#define DEBUG(x) {}
#define DEBUGV(x) {}
#define DEBUGA(x, y) {}
#define PRINTF(...) {}
#define CHECKPOINT {}
#endif
#define RESET(a, b) memset(a, b, sizeof a)
#define EPS 1e-9
#define m_p make_pair
#define pb push_back
#define fi first
#define se second
#define RALL(x) x.rbegin(), x.rend()
#define all(x) x.begin(), x.end()
#define ALL(x, y) x, x+y
#define SZ(x) ((int)x.size())
#define  pi(a)  pair<a, a> 
#define  vi(a)  vector<a> 
#define  vii(a) vector<pi(a)>
#define  vs vector<string>
template<class T> T sqr(T x){ return x*x; }
template<class T> T binPow(T p, int q, int MOD) {
    if(q == 1) return p % MOD;
    if(q & 1) return p*(binPow(p, q-1, MOD) % MOD) % MOD;
    else return sqr(binPow(p, q/2, MOD) % MOD) % MOD;
}
 
ll nxt() {
    ll temporaryVariable;
    cin >> temporaryVariable;
    return temporaryVariable;
}
const double PI = acos(-1.0);
#define MAXN 100001
const int G = 2e5 + 5;
 
 
 
int main(){
  ios::sync_with_stdio(false);

  int n;cin>>n;
  vii(int) v;
  
  REP(i,0,n){
      int x,y;cin>>x>>y;
      v.pb(m_p(x,y));
  }
  
bool flag=false,ok=true;

  for(int i=0;i<=(n-3);i++){
      
      ok=true; 
      int cnt=0;
      REP(j,i,i+3)
      {
          
        if(v[j].first==v[j].second && ok==true){
           cnt++;  
         }
         
        else {
         ok=false;
        }
     }
     if(cnt>=3)flag=true;
  }
 
  if(flag)
  cout<<"Yes"<<endl;
  else
  cout<<"No"<<endl;
 
    #ifdef HOHOHO   
    fprintf(stderr, "%.3lf\n", clock() / (double) CLOCKS_PER_SEC );
#endif
}
 



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

using namespace std;
static const int INF =(1<<21);


int main(){	
	string S;
	cin >> S;
	for(int i=0;i<3;i++)
		if (S[i] == 'A'&&S[i + 1] == 'C') {
			cout << "Yes" << endl;
			return 0;
		}
	cout << "No" << endl;
}

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

int main() {
    int n;
  cin>>n;
  int a[n];
    for(int k=0;k<n;k++){
      cin>>a[k];}
    
   int ruizyo2=0;
    for(int i=0;i<n;i++){
      while(a[i]%2==0){
        a[i]/=2;
        ruizyo2+=1;}
    }
  cout<<ruizyo2<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl "\n"
#define pb push_back
#define f(i,n) for(i=0;i<n;i++)
#define F(i,a,b) for(i=a;a<=b;i++)
#define arr(a,n) for( i=0;i<n;i++)cin>>a[i];
#define fi first
#define se second
#define mp make_pair
#define mod 1000000007
#define YES cout<<"YES"<<endl;
#define Yes cout<<"Yes"<<endl;
#define NO cout<<"NO"<<endl;
#define No cout<<"No"<<endl;
#define yes cout<<"yes"<<endl;
#define no cout<<"no"<<endl;
#define vi vector<ll>
#define ed end()
#define bg begin()
#define sz size()
#define ln length()
#define s() sort(a,a+n);
#define sr() sort(a,a+n,greater<ll>());
#define v()  sort(v.begin(),v.end());
#define vr() sort(v.begin(),v.end(),greater<ll>());
#define mod 1000000007
#define fast() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
ll gcd(ll a, ll b){if(!b)return a;return gcd(b, a % b);}
ll power(ll x,ll y,ll p){ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;}
int main() {
   /* #ifndef ONLINE_JUDGE
        // for getting input from input.txt
        freopen("input.txt", "r", stdin);
        // for writing output to output.txt
        freopen("output.txt", "w", stdout);
    #endif*/
        /* 
        Ofcourse it's Hard.
        It's supposed to be Hard.
        If it's easy everyone would do it.
        HARD IS WHAT MAKES IT GREAT

        YESTERDAY U SAID TOMORROW

        SLOWLY BECOMING THE PERSON I 
        SHOULD HAVE BEEN A LONG TIME AGO

        SAME TASK CAN'T BE FOUND DIFFICULT TWICE

        BTBHWSITW

        SPRH TU KAB P

        CP IS ALL ABOUT THINKING 
        YOU HAVE MUCH MORE POTENTIAL THAN U THINK

        AJIT SHIDDAT 10

        UR DAILY ROUTINE 


        */

fast();
//ll t;cin>>t;while(t--)
{
    ll a,b,c;
    cin>>a>>b>>c;
    cout<<min(b/a,c)<<endl;
}
return 0;
}

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

using ll = long long;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
#define ddrep(i, n) for (int i = n; i > 0; --i)
#define srep(i, s, t) for (int i = s; i < t; ++i)
#define ssrep(i, s, t) for (int i = s; i <= t; ++i)

#define rng(a) a.begin(), a.end()
#define rrng(a) a.rbegin(), a.rend()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second

#define chmax(x, y) (x = max(x, y))
#define chmin(x, y) (x = min(x, y))

using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using ld = long double;

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
    os << "(" << p.first << "," << p.second << ")";
    return os;
}

template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
    os << "{";
    rep(i, (int)v.size()) {
        if (i)
            os << ",";
        os << v[i];
    }
    os << "}";
    return os;
}

template <typename T, size_t S> void printArray(const T (&array)[S]) {
    for (auto val : array)
        std::cout << val << ", ";
    std::cout << "\n";
}

const int mod = 1e9 + 7;
const int inf = 1e9 + 5;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << std::setprecision(10);

    int n; std::cin >> n;
    vvi cost(n, vi(n, inf));
    rep(i, n) rep(j, n) {
        int a; std::cin >> a;
        cost[i][j] = a;
    }
    bool ok = true;
    ll ans = 0;
    rep(i, n) srep(j, i+1, n) {
        int c = inf;
        rep(k, n) if (k != i && k != j) {
            chmin(c, cost[i][k]+cost[k][j]);
        }
        if (c < cost[i][j]) ok = false;
        if (c > cost[i][j]) ans += cost[i][j];
    }
    std::cout << (ok ? ans : -1) << "\n";
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define show(x) cout<<x<<'\n'
#define showh(x) cout<<x<<' '
#define go(i,a,n) for(ll i=a;i<n;i++)
#define gor(i,a,n) for(ll i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define mod 1000000007
bool prime[100001];
bool ispoweroftwo(ll x)
{
    return x && !(x & (x-1));
}
ll xorcal(ll n)
{
    if(n%4==0)
        return n;
    if(n%4==1)
        return 1;
    if(n%4==2)
        return n+1;
    if(n%4==3)
        return 0;
}
void sieve(ll n)
{
    memset(prime,true,sizeof(prime));
    prime[0]=false;
    prime[1]=false;
    for(ll i=2;i*i<=n;i++)
    {
        if(prime[i]==true)
        {
            for(ll j=i*i;j<=n;j+=i)
            {
                prime[j]=false;
            }
        }
    }
}
bool isprime(ll n)
{
    if (n<=1) return false;
    if (n<=3) return true;

    if(n%2==0 or n%3==0) return false;

    for(ll i=5;i*i<=n;i+=6)
    {
        if(n%i==0 or n%(i+2)==0) return false;
    }
    return true;
}

ll modinverse(ll a,ll m)
{
    ll m0 = m;
    ll y = 0, x = 1;

    if (m == 1)
      return 0;

    while (a > 1)
    {
        ll q = a / m;
        ll t = m;

        m = a % m; a = t;
        t = y;

        y = x - q * y;
        x = t;
    }

    if (x < 0)
       x += m0;

    return x;
}

ll gcd(ll a,ll b)
{
    if(a==0)
    {
        return b;
    }
    return(b%a,a);
}
int main()
{
    fast
    ll n;
    cin>>n;
    ld sum=0,a;
    go(i,0,n){
        cin>>a;
        sum += ((ld)1/a);
    }
    sum = (ld)1/sum;
    cout<<fixed<<setprecision(20)<<sum;
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <climits>
#include <random>
#include <iomanip>

using namespace std;
using P = pair<long, long>;

typedef long long int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

#define fillInt(xs, x)        \
  for (int i = 0; i < (x); i++) \
    scanf("%d", &xs[i]);
#define fillLong(xs, x)       \
  for (int i = 0; i < (x); i++) \
    scanf("%ld", &xs[i]);
#define fillDouble(xs, x)       \
  for (int i = 0; i < (x); i++) \
    scanf("%lf", &xs[i]);
#define fillString(xs, x)       \
  for (int i = 0; i < (x); i++) \
    cin >> xs[i];
#define sortv(xs) sort(xs.begin(), xs.end())
#define sortvinv(xs) sort(xs.begin(), xs.end(), std::greater<long>())
#define lbv(xs, x) lower_bound(xs.begin(), xs.end(), x) - xs.begin()
#define ubv(xs, x) upper_bound(xs.begin(), xs.end(), x) - xs.begin()
#define bs(xs, x) binary_search(xs.begin(), xs.end(), x)
#define index_of(as, x) \
  distance(as.begin(), lower_bound(as.begin(), as.end(), x))
#define rad_to_deg(rad) (((rad)/2/M_PI)*360)
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define concat(xs, ys) (xs).insert((xs).end(), (ys).begin(), (ys).end())

const int mod = 1000000007;
const int MAX_V = 305;

struct road {
  int from;
  int to;
  long dist;

  bool operator>(road other) const {
    return dist > other.dist;
  }
};

long d[MAX_V][MAX_V];
long a[MAX_V][MAX_V];

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

  int n;
  cin >> n;

  rep(i, n) rep(j, n) {
    long dist;
    cin >> dist;

    d[i][j] = dist;
    a[i][j] = dist;
  }

  long res = 0;
  bool canDo = true;

  rep(k, n) rep(i, n) rep(j, n) {
    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
  }

  rep(i, n) for(int j = i+1; j < n; j++) {
    if (d[i][j] < a[i][j]) {
      canDo = false;
      break;
    }
    bool needHen = true;
    rep(k, n) {
      if (k == i || k == j) continue;
      if (d[i][k] + d[k][j] == a[i][j]) {
        needHen = false;
      }
    }
    if (needHen) {
      res += a[i][j];
    }
  }

  cout << (canDo?res:-1) << endl;
}

Measured memory_bytes: 2036
-- https://github.com/minoki/my-atcoder-solutions
{-# LANGUAGE TypeApplications #-}
import Data.Char (isSpace)
import Data.Int (Int64)
import qualified Data.Vector.Unboxed as U
import qualified Data.ByteString.Char8 as BS
import Data.Foldable

safeMul :: Int64 -> Int -> Maybe Int64
safeMul x y = let z = toInteger x * toInteger y
              in if z > 10^18
                 then Nothing
                 else Just $! fromInteger z

main = do
  n <- readLn @Int
  xs <- U.unfoldrN n (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
  let has_zero = U.any (== 0) xs
  let result = if has_zero then
                 0
               else
                 case U.foldM safeMul 1 xs of
                   Nothing -> -1
                   Just p -> p
  print result


Measured memory_bytes: 10576
/*
  D - 高橋君と見えざる手 / An Invisible Hand
  <http://abc047.contest.atcoder.jp/tasks/arc063_b>
*/

#include <stdio.h>

int main(int argc, char const *argv[]) {
  int N, T, A;
  int minA, maxProfits, cost;
  int i;

  minA = (int)1e+9+1;
  maxProfits = 0;
  cost = 0;

  scanf("%d %d", &N,&T);
  for( i=0; i<N; i++ ){
    scanf("%d", &A);
    if( minA >= A ){
      minA = A;
    }else if( maxProfits < (A - minA) ){
      maxProfits = A - minA;
      cost = 1;
    }else if( maxProfits == (A - minA) ){
      cost++;
    }
  }

  printf("%d\n", cost);

  return 0;
}


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

int main() {
    int N;
    cin >> N;
    int ex = 0;
    int up = 1;
    int sum = 0;
    for (int i = 1; i <= N; ++i) {
        sum += i;
        if (sum >= N) {
            ex = sum - N;
            up = i;
            break;
        }
    }
    for (int i = 1; i <= up; ++i) {
        if (i == ex) continue;
        cout << i << endl;
    }
}

Measured memory_bytes: 3592
N=int(input())
words=[]
flg=True

before=input()
words.append(before)
N=N-1

for i in range(N):
    s=input()
    if before[-1] != s[0]:
        flg=False
    words.append(s)
    before=s
if len(words) != len(set(words)):
    flg=False
print("Yes" if flg else "No")

Measured memory_bytes: 3060
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <utility>
#include <iomanip>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;
#define sz(x) (int) x.size()
#define unique(x) x.erase(unique(x.begin(), x.end()), x.end())
#define all(a) a.begin(), a.end()
#define sqr(x) ((x) * (x)) 
#define y1 aksjdaskdjksjfksdjf
#define left kdnvldvoiwejifejg
#define right lkdsjflksdjfdjfk
#define prev asdasfsadjkjsdfjs
#define tm aklsjdasjdasjdkdjjf
#define lcm hddalkwjeidjjhasda
#define random_shuffle asdasdd

const int MAXN = 2 * 105000;

int n;
string s;
set <int> st[26];
int r[MAXN][26];

int main() {

  getline(cin, s);
  n = sz(s);
  for (int i = 0; i < sz(s); i++) {
    st[s[i] - 'a'].insert(i);
  }

  for (int i = 0; i < 26; i++) {
    if (sz(st[i]) == 0) {
      cout << (char) ('a' + i) << endl;
      return 0;
    }
    auto lst = st[i].end();
    lst--;
    r[1][i] = *lst;
  }

  string ans = "";
  int ansLen = 0;
  int pos = -1;
  for (int i = 2; i <= n; i++) {
    int mn = n;
    for (int j = 0; j < 26; j++) {
      mn = min(mn, r[i - 1][j]);
    }
    for (int j = 0; j < 26; j++) {
      auto it = st[j].lower_bound(mn);
      if (it != st[j].begin()) {
        it--;
        r[i][j] = *it;
      } else {
        ansLen = i;
        pos = *st[j].begin();
        ans.append(1, 'a' + j);
        break;
      }
    }
    if (ansLen != 0) {
      break;
    }
  }

  for (int i = 0; i < ansLen - 1; i++) {
    for (int j = 0; j < 26; j++) {
      if (r[ansLen - 1 - i][j] > pos) {
        continue;
      }
      ans.append(1, 'a' + j);
      auto it = st[j].upper_bound(pos);
      if (it != st[j].end()) {
        pos = *it;
      }
      break;
    }
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 10628
#include <iostream>
#include <vector>
using namespace std;
int main()
{
	vector<int> data(5);
	int k;
	cin >> data[0];
	cin >> data[1];
	cin >> data[2];
	cin >> data[3];
	cin >> data[4];
	cin >> k;
	for(int i = 4; i > 0; i -= 1)
	{
		for(int j = i - 1; j >=0; j -= 1)
		{
			if(data[i] - data[j] > k)
			{
				cout << ":(" << endl;
				return 0;
			}
		}
	}
	cout << "Yay!" << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
typedef long long ll;
ll MOD = 1e9+7;

using namespace std;

int main()
{
	string s,t;
	string ans;
	bool ff=false;
	
	cin>>s;
	cin>>t;
	for(int i=0;i<s.length()-t.length()+1;i++)
	{
		bool f=true;
		for(int j=0;j<t.length();j++)
		{
			if(s[i+j]!='?' && s[i+j]!=t[j])
			{
				f=false;
				break;
			}
		}
		//書き換え
		if(f)
		{
			ff=true;
			ans = s;
			for(int j=0;j<i;j++)
			{
				if(ans[j]=='?')
					ans[j]='a';
			}
			for(int j=i;j<i+t.length();j++)
			{
				ans[j]=t[j-i];
			}
			for(int j=i+t.length();j<s.length();j++)
			{
				if(ans[j]=='?')
					ans[j]='a';
			}
		}
	}
	if(ff)
		cout<<ans<<endl;
	else
		cout<<"UNRESTORABLE"<<endl;
	return 0;
}

Measured memory_bytes: 256
/*ヽ｀、ヽ｀｀、ヽ｀ヽ｀、、ヽ ｀ヽ 、ヽ｀｀ヽヽ｀ヽ、ヽ｀
ヽ｀、ヽ｀｀、ヽ 、｀｀、 ｀、ヽ｀ 、｀ ヽ｀ヽ、ヽ ｀、ヽ｀｀、
ヽ、｀｀、｀、ヽ｀｀、 、ヽヽ｀、｀、、ヽヽ、｀｀、 、 ヽ｀、
ヽ｀｀、 ヽ｀ヽ｀、、ヽ ｀ヽ 、 ヽ｀｀｀｀ヽヽヽ｀、、ヽ｀、、ヽ*/
#include <bits/stdc++.h> 
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
 
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long   ll;
typedef long double ld;
typedef complex< ld > cd;
 
typedef pair<int, int> pi;
typedef pair<ll, ll>   pl;
typedef pair<ld, ld>   pd;
 
typedef vector< int > vi;
typedef vector< ld >  vd;
typedef vector< ll >  vl;
typedef vector< pi >  vpi;
typedef vector< pl >  vpl;
typedef vector< cd >  vcd;
 
#define l00p(i, a, b) for (int i=a; i<(b); i++)
#define loop(i, a)    for (int i=0; i<(a); i++)
#define rep1(i, a, b) for (int i = (b)-1; i >= a; i--)
#define rep(i, a)     for (int i = (a)-1; i >= 0; i--)
#define trav(a, x)    for (auto& a : x)
#define uid(a, b)     uniform_int_distribution<int>(a, b)(rng)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f  first
#define s  second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert
//#define MOD 998244353
 
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

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

const ld pii=3.14159265359; 
const int MOD = 1000000007;
const char nl = '\n';
const ll INF = 1e18;
const int MX = 100001; //check the limits, dummy

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); 
	ll n;
	cin>>n;
	cout<<(n*(n-1))/2;
	return 0;
}
// read the question correctly (ll vs int)
// template by bqi343

Measured memory_bytes: 3688
K, N = list(map(int, input().split()))
A = list(map(int, input().split()))

"""
5 - 0 #A1 - 0 i = 0
10 - 5#A2 -A1 i = 1
15 - 10#      i = 2
20 - 10  #K-A3 i = 3
"""
L = []
for i in range(N):
    if i == 0:
        continue
    else:
        L.append(A[i] - A[i - 1])
        
L.append(A[0] + K - A[N-1])

L = sorted(L, reverse=True)
del L[0]
print(sum(L))

Measured memory_bytes: 26444
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>

typedef long long ll;
using namespace std;

int N, A, B, C;
int l[1004];

int dfs(int cur, int a, int b, int c) {
    if (cur == N) {
        if (min(a, min(b, c)) > 0) return abs(a - A) + abs(b - B) + abs(c - C) - 30;
	    else return 1000000000;
	}
    int ret[4] = {0};

    ret[0] = dfs(cur + 1, a, b, c);
    ret[1] = dfs(cur + 1, a + l[cur], b, c) + 10;
    ret[2] = dfs(cur + 1, a, b + l[cur], c) + 10;
    ret[3] = dfs(cur + 1, a, b, c + l[cur]) + 10;
    
    return min(ret[0], min(ret[1], min(ret[2], ret[3])));
}


int main()
{

    cin >> N >> A >> B >> C;

    for (int i = 0; i < N; i++) {
        cin >> l[i];
    }

    cout << dfs(0, 0, 0, 0) << endl;


    return 0;
}

Measured memory_bytes: 256