akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T, class U> using Pa = pair<T, U>;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    int M = N*N;
    vec<int> P(M);
    for(int i=0;i<M;i++){
        cin >> P[i];
        P[i]--;
    }
    vec<int> dx = {-1,0,1,0},dy = {0,-1,0,1};

    int inf = 1e9;
    vvec<int> cost(N,vec<int>(N,inf));
    vvec<int> vis(N,vec<int>(N,1));

    for(int i=0;i<N;i++) for(int j=0;j<N;j++) {
        cost[i][j] = min({i,j,N-i-1,N-j-1});
    }

    auto in = [&](int x,int y){
        return 0<=x && x<N && 0<=y && y<N;
    };

    int ans = 0;
    for(auto& p:P){
        int sx = p/N,sy = p%N;
        ans += cost[sx][sy];
        vis[sx][sy] = 0;
        deque<Pa<int,int>> deq;
        deq.push_back({sx,sy});
        while(!deq.empty()){
            auto [x,y] = deq.front(); deq.pop_front();
            for(int k=0;k<4;k++){
                int nx = x+dx[k],ny = y+dy[k];
                if(!in(nx,ny)) continue;
                int nc = cost[x][y]+vis[x][y];
                if(cost[nx][ny]>nc){
                    cost[nx][ny] = nc;
                    if(vis[x][y]) deq.push_back({nx,ny});
                    else deq.push_front({nx,ny});
                }
            }
        }
    }
    cout << ans << "\n";
}

Measured memory_bytes: 7096
#include <stdio.h>
#include <string.h>
#include <math.h>

int main(void)
{
    int a, b, i, j, result = 0;
    char string[6];
    scanf("%d%d", &a, &b);

    for (i = a; i <= b; i++) {
        int num = 0, length, half_length;

        snprintf(string, 6, "%d", i);
        length = strlen(string);
        half_length = (int)ceil(length / 2.0);

        for (j = 0; j < half_length; j++) {
            if (string[j] != string[length - 1 - j]) {
                break;
            } else {
                num++;
            }
        }

        if (num == half_length) {
            result++;
        }
    }

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

    return 0;
}

Measured memory_bytes: 128
#include<stdio.h>

int main(){
	int a,b,c;
	int count=0;
	scanf("%d %d %d",&a,&b,&c);
	for(int i=a;i<=b;i++){
		if(c%i==0){
			count++;
		}
	}
	printf("%d\n",count);
	return 0;
}



Measured memory_bytes: 2112
using System;

namespace Atcoder1
{
    class Program
    {
        static void Main(string[] args)
        {
            double X = double.Parse(Console.ReadLine());
            double yokin = 100;
            int count = 0;

            do
            {
                yokin  = Math.Floor(yokin * 1.01);
                count += 1;
            } while (yokin < X);

            Console.WriteLine(count);
        }
    }
}

Measured memory_bytes: 27560
k =int(input())
seq = '1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51'
li =  list(map(int,seq.split(', ')))
print(li[k-1])

Measured memory_bytes: 38256
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define rep(i, n) repd(i, 0, n)

using namespace std;

namespace mp = boost::multiprecision;
using Bint = mp::cpp_int;

using ll = long long;
ll mod = pow(10, 9) + 7;

template <typename T> void output(T, ll);
ll gcd(ll, ll);
ll lcm(ll, ll);
Bint comb(Bint, Bint);
void prime_map(map<ll, ll> &, ll);

int main() {
    // source
    int a, b;
    int ans = 0;
    cin >> a >> b;
    repd(i, a, b + 1) {
        string temp = to_string(i);
        string temp_ = temp;
        reverse(temp.begin(), temp.end());
        if (temp == temp_) {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Bint comb(Bint a, Bint b) {
    Bint ans = 1;

    if (a < b) {
        return 0;
    }

    rep(i, b) {
        ans *= a - i;
        ans /= i + 1;
    }

    return ans;
}

template <typename T> void output(T a, int precision) {
    if (precision > 0) {
        cout << setprecision(precision) << a << "\n";
    } else {
        cout << a << "\n";
    }
}

template <typename T> T min(T a, T b) {

    if (a < b) {
        return a;
    } else {
        return b;
    }
}

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

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

void prime_map(map<ll, ll> &m, ll num) {

    if (num == 1) {
        return;
    }
    ll cache = num;
    repd(i, 2, sqrt(num) + 2) {
        if (num % i == 0) {
            if (m[i] == 0) {
                m[i] = 1;
            } else {
                m[i]++;
            }

            num /= i;
            break;
        }
    }
    if (cache == num) {
        if (m[num] == 0) {
            m[num] = 1;
        } else {
            m[num]++;
        }

        return;
    }
    prime_map(m, num);
    return;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <iostream>
#include <cmath>
#define maxn 100009
using namespace std;
int n;
char s[maxn];
int main(){
    scanf("%s",s);
    int n=strlen(s);
    if(s[0]==s[n-1]){
        if(n&1)
            puts("Second");
        else
            puts("First");
    }
    else{
        if(n&1)
            puts("First");
        else
            puts("Second");
    }
    //system("pause");
    return 0;
}



Measured memory_bytes: 384
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string.h>
#include <set>
#include <stack>

using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

template<class T> void printvec(const vector<T>& v) {
  for (auto x : v) { cout << x << " "; }
  cout << endl;
}
template<class T> void printtree(const vector< vector<T> >& tree) {
  for (long long i = 0; i < tree.size(); ++i) {
    cout << i + 1 << ": "; printvec(tree[i]);
  }
}
template<class T, class U> void printmap(const map<T, U>& mp) {
  for (auto x : mp) { cout << x.first << "=>" << x.second << endl; }
}

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

#define rep(i, n) for(ll i = 0; i < n; ++i)
#define all(s) s.begin(), s.end()
#define sz(x) (ll)(x).size()
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> triple;
typedef double D;
typedef vector<ll> vl;
typedef vector<P> vp;

const ll INF = 1e9;
const ll MOD = 1000000007;  // 1e9 + 7

int main(int argc, char** argv) {
  cin.tie(NULL);
  cout.tie(NULL);
  ios_base::sync_with_stdio(false);
  //cout << setprecision(10) << fixed;

  ll n,m,k;
  cin >> n >> m >> k;
  vector<ll> a(n), b(m);
  rep(i,n) {
    cin >> a[i];
  }
  rep(i,m) {
    cin >> b[i];
  }

  vector<ll> s(n+1);
  rep(i,n) {
    s[i+1] = s[i] + a[i];
  }
  vector<ll> sb(m+1);
  rep(i,m) {
    sb[i+1] = sb[i] + b[i];
  }

  ll ans = 0;
  // Here, calculate max for each a
  rep(i,n+1) {
    ll now = i; // read i.

    ll remain = k - s[i];
    if (remain < 0) { break; } // too small
    // Here, remain >= 0

    // prev of upper_bound
    auto it = upper_bound(all(sb), remain);
    if (it == sb.begin()) { // invalid
      continue;
    } else {
      ll idx = prev(it) - sb.begin(); // idx of sb. sb[idx] <= remain
      now += idx;
      chmax(ans, now);
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 9532
#include<iostream>
#include<vector>
#include<numeric>
#include<algorithm>
#include<cmath>

using namespace std;

int par[123];
int x[123],y[123],z[123],r[123];

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

void unite(int a,int b){
  par[find(a)]=find(b);
}

double sqr(double d){
  return d*d;
}

double dist(int i,int j,double zz){
  return sqrt(r[i]*r[i]-sqr(z[i]-zz))+sqrt(r[j]*r[j]-sqr(z[j]-zz));
}

double cross(int i,int j,double bm){
  double d=dist(i,j,bm);
  return sqr(x[i]-x[j])+sqr(y[i]-y[j])-d*d<0;
}

int main(){
  for(int n;cin>>n,n;){
    vector<double> cz{0,1e9};
    for(int i=0;i<n;i++){
      cin>>x[i]>>y[i]>>z[i]>>r[i];
      cz.push_back(z[i]+r[i]);
      cz.push_back(z[i]-r[i]);
      for(int j=0;j<i;j++){
	if(sqr(x[i]-x[j])+sqr(y[i]-y[j])+sqr(z[i]-z[j])<sqr(r[i]+r[j])){
	  int rl=max(z[i]-r[i],z[j]-r[j]),rh=min(z[i]+r[i],z[j]+r[j]);
	  double l=rl,h=rh;
	  for(int k=0;k<99;k++){
	    double lh=(h-l)/3+l,hl=(h-l)*2/3+l;
	    if(dist(i,j,lh)<dist(i,j,hl)){
	      l=lh;
	    }else{
	      h=hl;
	    }
	  }
	  double bl=rl,bh=l;
	  double tl=l,th=rh;
	  for(int k=0;k<99;k++){
	    double bm=(bh+bl)/2;
	    if(cross(i,j,bm)){
	      bh=bm;
	    }else{
	      bl=bm;
	    }
	    double tm=(tl+th)/2;
	    if(cross(i,j,tm)){
	      tl=tm;
	    }else{
	      th=tm;
	    }
	  }
	  //	  cout<<rl<<' '<<l<<' '<<rh<<' '<<bl<<' '<<tl<<endl;
	  cz.push_back(bl);
	  cz.push_back(tl);
	}
      }
    }
    sort(begin(cz),end(cz));
    vector<int> ns{0};
    for(int i=0;i<cz.size()-1;i++){
      double m=(cz[i]+cz[i+1])/2;
      iota(begin(par),end(par),0);
      for(int i=0;i<n;i++){
	if(r[i]*r[i]>sqr(z[i]-m)){
	  for(int j=0;j<i;j++){
	    if(r[j]*r[j]>sqr(z[j]-m)&&cross(i,j,m)){
	      unite(i,j);
	    }
	  }
	}else{
	  par[i]=-1;
	}
      }
      bool u[123]={};
      int ncs=0;
      for(int i=0;i<n;i++){
	if(par[i]>=0){
	  ncs+=!u[find(i)]++;
	}
      }
      //      cout<<m<<' '<<ncs<<endl;
      if(ncs!=ns.back()){
	ns.push_back(ncs);
      }
    }
    cout<<ns.size()-1<<endl;
    for(int i=0;i<ns.size()-1;i++){
      cout<<(ns[i+1]-ns[i]==1);
    }
    cout<<endl;
  }
}

Measured memory_bytes: 1228
#include<cstdio>
#include<cstring>

int main(){
    char s[200001];
	scanf("%s",s);
	int a,z;
	for(int i = 0; ; i++){
		if(s[i] == 'A'){
			a =i;
			break;
		}
	}
	for(int i = strlen(s); ; i--){
		if(s[i]=='Z'){
			z = i;
			break;
		}
	}

	printf("%d\n",z - a + 1);

	return 0;
}

Measured memory_bytes: 384
# coding=utf-8
# Date: 2020-01-08
# Author: lee215
get = lambda: int(input().strip())
getl = lambda: input().strip()
gets = lambda: list(map(int, input().strip().split()))
getss = lambda n: [gets() for _ in range(n)]

H, N = gets()
AB = getss(N)
AB.sort(key=lambda a_b: -a_b[0] * 1.0 / a_b[1])

a0, b0 = AB[0]
dp = [0] + [float('inf')] * (H + a0)

cur = 0
while cur <= H + a0:
    dp[cur] = cur // a0 * b0
    cur += a0


for a, b in AB[1:]:
    for i in range(a, H + a0 + 1):
        dp[i] = min(dp[i], dp[i - a] + b)
print(min(dp[H:]))


Measured memory_bytes: 50012
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
long long n,a,b[1000000],c,p;
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		scanf("%d",&a);if(b[0]==1 || c>a){cout<<"No"<<endl;continue;}
		if(c==a && p!=a){cout<<"No"<<endl;continue;}p++;
		if(a>=1000000){cout<<"Yes"<<endl;continue;}
		b[a]++;while(b[a]>=2){b[a]-=2;b[a-1]++;a--;p--;}
		while(c<=999998 && b[c+1]==1)c++;
		cout<<"Yes"<<endl;
	}
	return 0;
}

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

const double PI = acos(-1);

int main()
{
  int a, b, h, m;
  cin >> a >> b >> h >> m;

  double th = double(h * 60 + m) / 720 * 2 * PI;
  double tm = double(m) / 60 * 2 * PI;
  double xh = a * sin(th), yh = a * cos(th);
  double xm = b * sin(tm), ym = b * cos(tm);
  double dx = xh - xm, dy = yh - ym;
  double ans = sqrt(dx * dx + dy * dy);
  printf("%.10f\n", ans);

  return 0;
}

Measured memory_bytes: 4068
#include <stdio.h>
#include <stdlib.h>
#define N 100
#define A_IN 100

int main(){
  int i,j,flag,A[N],n,tmp,count=0,minj;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }

  for(i=0;i<n-1;i++){
    minj=i;
    for(j=i;j<n;j++){
      if(A[j]<A[minj]){
	minj=j;
      }
    }
	tmp=A[i];
	A[i]=A[minj];
	A[minj]=tmp;
	if(i!=minj)count++;
  }
  for(i=0;i<n;i++){
    if(i==n-1)printf("%d\n%d\n",A[i],count);
    else printf("%d ",A[i]);
  }

  return 0;
}



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

#define GO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int

const int maxr = 1e5 + 5;


int32_t main()
{
	GO;
	string s;
	cin >> s;
	cout << s[0] << s[1] << s[2] << endl;
	return 0;
}

//!

Measured memory_bytes: 3636
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <deque>
#include <cctype>
#include <cstdio>
#include <math.h>
#include <set>
#define INF 1000000000000
using namespace std;
using ll = long long;
int main(){
    string s,t;
    cin >> s >> t;
    vector<ll> a(26,-1);
    vector<ll> b(26,-1);
    for(ll i=0;i<s.length();i++){
        int num = s[i]-'a';
        int num2 = t[i]-'a';
        if(a[num2]==-1){
            a[num2] = num;
        }else{
            if(a[num2]!=num){
                cout << "No" << endl;
                return 0;
            }
        }
        if(b[num]==-1){
            b[num] = num2;
        }else{
            if(b[num]!=num2){
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;
}

Measured memory_bytes: 776
#include <stdio.h>
int main()
{
    int N,i,candies=0;
     scanf("%d",&N);
       if(N>=1 && N<=100)
       {
       for(i=1;i<=N;i++)
        {
            candies = candies+i;
        }
       }
          printf("%d\n",candies);
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <set>

using namespace std;

int main() {
  int N, A;
  set<int> S;

  cin >> N;

  for (int i = 0; i < N; i++) {
    cin >> A;
    if (S.erase(A) == 0) {
      S.insert(A);
    }
  }

  cout << S.size() << endl;

  return 0;
}


Measured memory_bytes: 4864
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  string s;
  int n,i,kotae=1;
  cin>>s;
  n=s.length();
  for(i=0;i<=(n-3)/4;i++){
    if(s[i]==s[n-1-i]&&s[(n+1)/2+i]==s[(n-3)/2-i]&&s[i]==s[(n+1)/2+i]){
    }else{
      kotae=0;
    }
  }
  if(kotae){
    cout<<"Yes";
  }else{
    cout<<"No";
  }
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.IntStream;

/**
 * 解説通りに作成したソースコード
 * 
 * https://atcoder.jp/contests/abc122/submissions/4696453 にも参考
 */
public class Main {

	/** 文字の種類数 */
	private static final int N = 4;

	private static final long MOD = 1_000_000_007L;

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int n = scanner.nextInt();
			long[][][][] memo = new long[N + 1][N + 1][N + 1][n];
			IntStream.rangeClosed(0, N).forEach(i -> IntStream.rangeClosed(0, N)
					.forEach(j -> IntStream.rangeClosed(0, N).forEach(k -> Arrays.fill(memo[i][j][k], -1))));
			System.out.println(dp(n, N, N, N, 0, memo));
		}
	}

	/**
	 * 処理結果を再帰的に計算する
	 * 
	 * @param n     総文字数
	 * @param x1    三つ前の文字（0:A、1:C、2:G、3:T、4:その他）
	 * @param x2    二つ前の文字（0:A、1:C、2:G、3:T、4:その他）
	 * @param x3    一つ前の文字（0:A、1:C、2:G、3:T、4:その他）
	 * @param index 現在処理している文字の場所
	 * @param memo  処理結果を保存する配列
	 * @return 処理結果
	 */
	private static long dp(int n, int x1, int x2, int x3, int index, long[][][][] memo) {
		if (n == index) {
			return 1L;
		}
		if (memo[x1][x2][x3][index] >= 0) {
			return memo[x1][x2][x3][index];
		}
		long answer = 0L;
		for (int next = 0; next < N; next++) {
			if (ok(x1, x2, x3, next) && ok(x1, x2, next, x3) && ok(x1, x3, x2, next) && ok(x2, x1, x3, next)) {
				answer = (answer + dp(n, x2, x3, next, index + 1, memo)) % MOD;
			}
		}
		return memo[x1][x2][x3][index] = answer;
	}

	/**
	 * x1x2x3x4で組合せた文字列に「AGC」が含まれないかをチェックする
	 * 
	 * @param x1 一つ目の文字（0:A、1:C、2:G、3:T、4:その他）
	 * @param x2 二つ目の文字（0:A、1:C、2:G、3:T、4:その他）
	 * @param x3 三つ目の文字（0:A、1:C、2:G、3:T、4:その他）
	 * @param x4 四つ目の文字（0:A、1:C、2:G、3:T、4:その他）
	 * @return x1x2x3x4で組合せた文字列に「AGC」が含まれない場合true
	 */
	private static boolean ok(int x1, int x2, int x3, int x4) {
		return !((0 == x1) && (2 == x2) && (1 == x3)) && !((0 == x2) && (2 == x3) && (1 == x4));
	}
}


Measured memory_bytes: 38400
#include<stdio.h>

#define N 100

int main(){
  int key[N][N];
  int n,i,j,m,l,o;

  scanf("%d",&n);

  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      key[i][j]=0;
    }
  }

  for(i=0;i<n;i++){
     scanf("%d%d",&m,&l);
    m--;
    for(j=0;j<l;j++){
      scanf("%d",&o);
      o--;
      key[m][o]=1;
    }
  }

  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      if(j>0) printf(" ");
      printf("%d",key[i][j]);
    }
    printf("\n");
  }

  return 0;
}



Measured memory_bytes: 2128
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#include<sstream>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef pair<int,pii> pip;
typedef vector<pip>vip	;
const double PI=acos(-1);
const double EPS=1e-8;
const int inf=1e8;
int dx[]={1,1,1,0,0,-1,-1,-1};
int dy[]={1,0,-1,1,-1,1,0,-1};
int main(){
	int n,m;
	while(cin>>n>>m,n+m){
		vector<string>in(n);
		rep(i,n)cin>>in[i];
		set<string>out1,out2;
		string out="";
		rep(i,n)rep(j,m)rep(k,8){
			int sx=i,sy=j;
			string s="";
			s+=in[sx][sy];
			int nx=(sx+dx[k]+n)%n,ny=(sy+dy[k]+m)%m;
			while(nx!=sx||ny!=sy){
				s+=in[nx][ny];
				nx=(nx+dx[k]+n)%n,ny=(ny+dy[k]+m)%m;
				if(out1.find(s)!=out1.end()){
					if(out.size()==s.size()){
						if(s<out)out=s;
					}else if(out.size()<s.size()){
						out=s;
					}
				}else out1.insert(s);
			}
		}
		if(out=="")cout<<0<<endl;
		else cout<<out<<endl;
	}
}

Measured memory_bytes: 33768
#include<iostream>
#include<algorithm>
using namespace std;
const int MAX=300005;
int tree[MAX],n,m;
pair<int,int> query[MAX];
int cmp(pair<int,int> a,pair<int,int> b)
{
	return a.second-a.first<b.second-b.first;
}
void update(int r,int key)
{
	for(;r<=m;r+=(r&(-r))){
		tree[r]+=key;
	}
}
int getBIT(int r)
{
	int result=0;
	while(r>0){
		result+=tree[r];
		r-=(r&(-r));
	}
	return result;
}
int main()
{
	int a,b;
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		cin>>query[i].first>>query[i].second;
	}
	sort(query+1,query+n+1,cmp);
	int idx=1;
	for(int d=1;d<=m;++d){
		for(;idx<=n&&d>query[idx].second-query[idx].first+1;++idx){
			update(query[idx].first,1);
			update(query[idx].second+1,-1);
		}
		int ans=n-idx+1;
		for(int i=d;i<=m;i+=d){
			ans+=getBIT(i);
		}
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 3712
#include <iostream>
#include <bits/stdc++.h>
#include <vector>
#include <utility>
#include <string>
#include <math.h>
#include <algorithm>
#include <cstring>
#include <cctype>

typedef long long int ll;
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素


using namespace std;

int main() {
   
   long long int X,K,D;
   cin >> X >> K >> D;

   long long int pos=X;

   long long int p= fabs(X)/D;

   // cout << p << endl;
   if(K < p){
      pos = fabs(X)-fabs(K*D); 
   }else{
      if((K-p)%2==0){
         pos = fabs(X)-fabs(p*D);
      }else{
         pos = fabs(X)-fabs((p+1)*D);
      }
   }
   long long int A = fabs(pos);
   printf("%lld\n",A);
   // cout <<  <<endl;

}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
void rd(int &x){
  int k, m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
void wt_L(const char c[]){
  int i=0;
  for(i=0;c[i]!='\0';i++){
    putchar_unlocked(c[i]);
  }
}
int A, N;
int main(){
  rd(N);
  rd(A);
  if(N%500 <= A){
    wt_L("Yes");
    putchar_unlocked('\n');
  }
  else{
    wt_L("No");
    putchar_unlocked('\n');
  }
  return 0;
}
// cLay varsion 20180208-1

// --- original code ---
// int N, A;
// {
//   rd(N,A);
//   if(N%500 <= A) wt("Yes"); else wt("No");
// }


Measured memory_bytes: 256
/*
   Created by Rahul Goel.
*/
/*******************************************************************************/
#include <iostream>
#include <vector>
#include <numeric>
#include <cstring>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
/*******************************************************************************/
using namespace std;
using ll = long long;
using ld = long double;
const ll mod = 1000000007;
const int INF = 1e9;
const ll LINF = 1e18;
/*******************************************************************************/
/*
.-.. . -. -.- .- / .. ... / .-.. --- ...- . -.-.--
 */
/* For PBDS */
/*Two new methods X.order_of_key() and X.find_by_order()*/
/*
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/

/*******************************************************************************/
ll mod_sum() { return 0LL; }
template<typename T, typename... Args>
T mod_sum(T a, Args... args) { return ((a + mod_sum(args...))%mod + mod)%mod; }

ll mod_prod() { return 1LL; }
template<typename T, typename... Args>
T mod_prod(T a, Args... args) { return (a*mod_prod(args...))%mod; }
/*******************************************************************************/
using pii = pair < ll, ll >;
using vi = vector < ll >;
using vb = vector < bool >;
using vvi = vector < vector < ll > >;
using vvb = vector < vector < bool > >;
using vpii = vector < pii >;
using vvpii = vector < vector < pii > >;
#ifdef ONLINE_JUDGE
#define endl '\n'
#endif
#define fastio          ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(c)          (c).begin(), (c).end()
#define present(c,x)    ((c).find(x) != (c).end())
#define cpresent(c,x)   (find(all(c),x) != (c).end())
#define uniq(c)         (c).resize(distance((c).begin(), unique(all(c))))
#define min_pq(t)       priority_queue < t, vector < t >, greater < t > >
#define max_pq(t)       priority_queue < t >
#define pb              push_back
#define ff              first
#define ss              second
/*******************************************************************************/

/*
    Code begins after this.
*/


ll solve(){
    ll n;
    cin >> n;
    vi vec(n + 1);
    for(ll i = 1; i <= n; i++)
        cin >> vec[i];
    ll ans = 0;
    for(ll i = 1; i <= n; i++)
        if((i & 1) && (vec[i] & 1))
            ans++;
    cout << ans << endl;
    return 0;
}


signed main(){
    fastio;

    ll t = 1;
    while(t--)
        solve();

    return 0;
}

/*******************************************************************************/
// Remeber - In a custom comparator cmp(a, b) a==b must always return to false.



Measured memory_bytes: 3672
import sys
sys.setrecursionlimit(1000000)

class UnionFind:
	def __init__(self, n=1):
		self.par = [ i for i in range(n)]
		self.size = [0] * n

#   木の根を求める
	def root(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.root(self.par[x])
			return self.par[x]


#   x を含むグループと y を含むグループをマージする
	def merge(self, x, y):
		x = self.root(x)
		y = self.root(y)
		if x == y:
			return
		self.par[x] = y

if __name__ == '__main__':
	N, M = map(int, input().split())
	uf = UnionFind(N)
	for i in range(M):
		X, Y, Z = map(int, input().split())
		uf.merge(X-1, Y-1)
	
	ans = [ uf.root(i) for i in range(N)]

	print(len(set(ans)))

Measured memory_bytes: 30760
# AGC032A - Limited Insertion
def main():
    # last manipulation <-> rightmost number which corresponds with its index
    n = int(input())
    B = list(map(int, input().rstrip().split()))
    ans = []
    while len(B) > 0:
        for i in range(len(B) - 1, -1, -1):
            if B[i] == i + 1:
                ans += [B.pop(i)]
                break
        else:  # invalid sequence
            print(-1)
            return
    print(*ans[::-1], sep="\n")


if __name__ == "__main__":
    main()

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

int main()
{
    long long a,b,diff;

    cin>>a>>b;

    if(a<=0 && b>=0)cout<<"Zero";

    else if(a>=0 && b>=0)cout<<"Positive";

    else
    {
        diff = b-a;
        if(diff%2==0)
            cout<<"Negative";
        else cout<<"Positive";
    }
}


Measured memory_bytes: 256
// stay fuckin hard -- Abhinav -IIITA
#include<bits/stdc++.h>
#define int long long
#define ld long double
using namespace std;
int mod=1e9+7;
ld pi=3.1415926535;
int fun(int a,int b){
	int r=1;
	while(b>0){
		if(b&1){
			r*=a;
			r%=mod;
		}
		b/=2;
		a*=a; a%=mod;
	}
	return r;
}
int32_t main(){
	int n,k; cin>>n>>k;
	int ans=0;
	int dp[k+1]={0};
	for(int i=k;i>0;--i){
		dp[i]=fun((k/i),n);
		for(int ii=2*i;ii<=k;ii+=i){
			dp[i]-=dp[ii]; 
		}
		dp[i]+=mod; dp[i]%=mod;
		ans+=(i*dp[i])%mod; ans+=mod; ans%=mod;
	}
	cout<<ans;
	return 0;
}


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

int main() {
  int N;
  cin >> N;
  vector<int> a(N);
  for (int i=0;i<N;i++){
    cin >> a[i];
  }
  vector<int> ball(N,0);
  for (int i=N-1;i>=0;i--){
    int count=0;
    for (int j=2;(i+1)*j<=N;j++){
      if (ball[(i+1)*j-1]==1){
        count++;
      }
    }
    if (count%2==a[i]){
      ball[i]=0;
    }
    else {
      ball[i]=1;
    }
  }
  vector<int> ans(N);
  int s=0;
  for (int i=0;i<N;i++){
    if (ball[i]==1){
      ans[s]=i+1;
      s++;
    }
  }
  cout << s << endl;
  for (int i=0;i<s;i++){
    cout << ans[i];
    if (i!=s-1){
      cout << ' ';
    }
    else {
      cout << endl;
    }
  }
}

Measured memory_bytes: 3200
#![allow(unused_imports)]

use proconio::{input, fastout};
use proconio::marker::*;

#[fastout]
fn main() {
    input! {
    a: f64,
    b: f64,
    x: f64
    }
    let ans = 90.0 - if a * b / 2.0 < x / a {
        a.powf(3.0) / (2.0 * (b * a * a - x))
    } else {
        2.0 * x / (a * b * b)
    }.atan() * 180.0 / std::f64::consts::PI;
    println!("{}", ans);
}


Measured memory_bytes: 3060
from math import ceil
dg=list(map(int,input().split()))
pc=[]
ans=0
for i in range(dg[0]):
    pc.append(list(map(int,input().split())))
    ans+=pc[-1][0]
pattern=2**dg[0]
for i in range(2**dg[0]):
    for j in range(dg[0]):
        p=bin(pattern+i)[3:]
        tsum=0
        tans=0
        for k in range(dg[0]):
            if k==j:
                pass
            else:
                if p[k]=="0":
                    tsum+=(1+k)*100*pc[k][0]+pc[k][1]
                    tans+=pc[k][0]
        if tsum<dg[1]:
            dtans=min(pc[j][0]-1,ceil((dg[1]-tsum)/((1+j)*100)))
            tsum+=((1+j)*100)*dtans
            tans+=dtans
        if tans<ans and tsum>=dg[1]:
            ans=tans
print(ans)


Measured memory_bytes: 3192
#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
#include<string.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
long long int mod=1e9+7;
bool debug=false;
typedef long long ll;
int main(){
	string s;
	cin>>s;
	vector<long long int>dp(13,0);
	vector<long long int>tmp(13,0);
	int num;
	dp[0]=1;
	rep(i,s.size()){
		rep(j,13){
			tmp[j]=dp[j];
		}
		rep(j,13){
			dp[(j*10)%13]=tmp[j];
		}
		rep(j,13){
			tmp[j]=dp[j];
		}
		if(s[i]=='?'){
			rep(j,13){
				for(int k=1;k<10;k++){
					dp[(j+k)%13]=(dp[(j+k)%13]+tmp[j])%mod;
				}
			}
		}else{
			num=s[i]-'0';
			rep(j,13){
				dp[(j+num)%13]=tmp[j];
			}
		}
	}
	cout<<dp[5]<<endl;
	/*
	rep(i,13){
		cout<<i<<"<="<<dp[i]<<endl;
	}
	*/


	return 0;
}

Measured memory_bytes: 512
N,M = map(int,input().split())
box = [float('inf')]*(2**N)

for i in range(M):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    k = 0
    for i in c:
        k += 2**(i-1)
    box[k] = min(box[k],a)
    for j in range(2**N):
        box[(k&j)+(k^j)] = min(box[(k&j)+(k^j)],box[k]+box[j])
if box[-1] == float('inf'):
    print(-1)
else:
    print(box[-1])

Measured memory_bytes: 50908
#include<cstdio>
typedef long long LL;
const int N=100000;
const int L=200000;
int n,x,y;
int fa[L+5];
int cntx[L+5],cnty[L+5];
LL ans;
int Find(int x) {
	if(fa[x]==x) return x;
	return fa[x]=Find(fa[x]);
}
int main() {
	for(int i=1;i<=L;i++)
		fa[i]=i;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%d %d",&x,&y);
		int fx=Find(x),fy=Find(y+N);
		if(fx!=fy) fa[fy]=fx;
	}
	for(int i=1;i<=L;i++) {
		int fi=Find(i);
		if(i<=N) cntx[fi]++;
		else cnty[fi]++;
	}
	for(int i=1;i<=L;i++)
		ans+=(LL)cntx[i]*cnty[i];
	printf("%lld\n",ans-n);
	return 0;
}

Measured memory_bytes: 2048
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define forinc(a,b,c) for(int a=b;a<=c;++a)
#define fordec(a,b,c) for(int a=b;a>=c;--a)
#define forv(a,b) for(auto &a:b)
#define pb push_back
#define mp make_pair
#define ii pair<int,int>
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define reset(f,x) memset(f,x,sizeof(f))
#define vt vector<int>
#define vpi vector<pair<int,int>>
#define bit(x,i) (x>>(i-1)&1ll)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1ll<<(i-1)))
#define task ""
#define int long long
template<typename X,typename Y>void Min(X &x,Y y){x=(x>y)?y:x;}
template<typename X,typename Y>void Max(X &x,Y y){x=(x<y)?y:x;}
template<typename X>void read(X &x){x=0;int n=0;char c=getchar();for(;!isdigit(c);c=getchar())n+=(c=='-');for(;isdigit(c);c=getchar())x=x*10+c-'0';x=(n&1)?-x:x;}
template<typename X,typename... Y>void read(X &x,Y&... y){read(x);read(y...);}
const int N=2e5+5;
int n,a[N],s[N];
int ans=LLONG_MAX;
main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
   // freopen("b.inp","r",stdin);
    cin>>n;
    forinc(i,1,n) cin>>a[i];
    forinc(i,1,n) s[i]=s[i-1]+a[i];
    forinc(i,1,n) ans=min(ans,abs(s[i]-(s[n]-s[i])));
    cout<<ans;
}


Measured memory_bytes: 3456
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define maxs(a, b) a = max(a, b)
#define mins(a, b) a = min(a, b)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll linf = (1ll << 61);
const int inf = 1001001001;
const int mod = 1000000007;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<int> a(n), b(n), c(n - 1);
	rep(i, n) cin >> a[i];
	rep(i, n) cin >> b[i];
	rep(i, n - 1) cin >> c[i];
	int ans = 0;
	int prev = -2;
	rep(i, n) {
		ans += b[a[i] - 1];
		if (prev + 1 == a[i] - 1) {
			ans += c[a[i - 1] - 1];
		}
		prev = a[i] - 1;
	}
	printf("%d\n", ans);
	return 0;
}


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

int main(){
    string s;
    cin >> s;
    if(s[1] == 'R') cout << "ABC" << endl;
    else cout << "ARC" << endl;
    return 0;
}

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

void outerLoop(int i);
void innerLoop(int i, int j);

static const int MAX = 9;

int main()
{
    outerLoop(1);
}

void outerLoop(int i)
{
    if (MAX < i) {
        return;
    }
    innerLoop(i, 1);
    outerLoop(i + 1);
}

void innerLoop(int i, int j)
{
    if (MAX < j) {
        return;
    }
    cout << i << "x" << j << "=" << i * j << endl;;
    innerLoop(i, j + 1);
}

Measured memory_bytes: 2996
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <iostream>
#include <fstream>
#include <numeric>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <cmath>
#include <set>
#include <map>
#include <functional>
#include <bitset>
#include <iomanip>
#include <stack>
#include <list>
#include <cstdint>
#include <chrono>

using namespace std;
#define     loop(n,i,a)     for(ll i=a;i<n;i++)
#define     loopR(n,i,a)    for(ll i=a-1;i>=n;i--)
#define     all(arr,n)      arr,arr+n
#define     allv(v)         (v).begin(),(v).end()
#define     rallv(v)        (v).rbegin(),(v).rend()
#define     m_p             make_pair
#define     ll              long long
#define     pii             pair<ll,ll>
#define     vi              vector<int>
#define     vll             vector<ll>
#define     vii             vector<pii>
#define     sz(x)           (int)x.size()
#define     pb              push_back
#define     endl            "\n"
#define     Endl            "\n"
#define     f               first
#define     s               second
#define     mem(dp,n)       memset(dp,n,sizeof dp)
int dx[] = { 1 , 0 ,-1 , 0 ,-1 ,-1 , 1 , 1 };
int dy[] = { 0 , 1 , 0 ,-1 ,-1 , 1 ,-1 , 1 };
int KnightI[] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int KnightJ[] = { 1, 2, 2, 1, -1, -2, -2, -1 };
template<typename T>
void max_self(T &a,T b){
    a=max(a,b);
}
template<typename T>
void min_self(T &a,T b){
    a=min(a,b);
}
void fast(){
    std::ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}
vector<string> vec_splitter(string s) {
    s += ',';
    vector<string> res;
    while(!s.empty()) {
        res.push_back(s.substr(0, s.find(',')));
        s = s.substr(s.find(',') + 1);
    }
    return res;
}
void debug_out(
        vector<string> __attribute__ ((unused)) args,
        __attribute__ ((unused)) int idx,
        __attribute__ ((unused)) int LINE_NUM) { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
    if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
    stringstream ss; ss << H;
    cerr << args[idx] << " = " << ss.str();
    debug_out(args, idx + 1, LINE_NUM, T...);
}
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
const ll mxN=5e5+10,oo=0x3f3f3f3f,MOD=998244353;
const double PI = acos(-1);

void solve(){
    int n;
    cin>>n;
    map<ll,ll>mp;
    ll sum=0;
    loop(n,i,0){
        ll x;
        cin>>x;
        sum+=x;
        mp[sum]++;
    }
    mp[0]++;
    ll res=0;
    for(auto x:mp)
        res+=(x.s*(x.s-1)/2);
    cout<<res<<endl;
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    fast();
    solve();

}


Measured memory_bytes: 16080
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>

#define CK(N,A,B) (A<=N&&N<B)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define RREP(i,a,b) for(int i=(b-1);a<=i;i--)
#define F first
#define S second
#define ll long long;

const int INF = 1e9;
const long long  LLINF = 1e15;

using namespace std;

set<int> dp[26];

string S;

int main() {
  cin>>S;
  int cnt = 0;
  while(1){
    REP(i,0,S.size()){
      dp[S[i]-'a'].insert(max(0, i-cnt));
    }
    REP(i,0,26){
      bool flag = true;
      REP(j,0,S.size()-cnt){
        if(dp[i].find(j) == dp[i].end())flag = false;
      }
      if(flag){
        cout<<cnt<<endl;
        return 0;
      }
    }
    cnt++;
  }
  return 0;
}


Measured memory_bytes: 256
class UnionFind:
    def __init__(self, n):
        #親要素のノード番号を格納。par[x] == xのときそのノードはroot
        self.par = [i for i in range(n)]
        #木の高さ（初期状態では0）
        self.rank = [0] * n

    def find(self, x):
        #木の根を求める
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def same(self, x, y):
        # xとyが同じ集合に属するかを判定
        return self.find(x) == self.find(y)

    def union(self, x, y):
        #併合する
        #まず根を探す
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
V, E = map(int, input().split())
nodes = sorted([list(map(int, input().split())) for _ in range(E)], key = lambda x: x[2])

a = UnionFind(V)
ans = 0
for node in nodes:
    si, ti = node[0] - 1, node[1] - 1
    if not a.same(si, ti):
        a.union(si, ti)
        ans += node[2]

print(ans)


Measured memory_bytes: 28992
#include<stdio.h>
#include<math.h>
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main()
{
	string N;
	if (cin >> N)
	{
		int a = 0;
		for (const auto& i : N)
		{
			a += i - '0';
		}
		if (a % 9 > 0)
		{
			cout << "No" << endl;
		}
		else
		{
			cout << "Yes" << endl;
		}
	}
}

Measured memory_bytes: 3712
import itertools
import bisect

N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
B = B + [10**10]

Ac = list(itertools.accumulate(A))

iA = bisect.bisect_right(Ac,K)

A_ok = Ac[:iA][::-1]+[0]
Alen = len(A_ok)

ans = 0
SUM = 0
cnt = 0
for i in range(Alen):
    K2 = K - A_ok[i]
    k = cnt
    for j in range(M-k):
        if SUM + B[j+k] <= K2:
            cnt += 1
            SUM += B[j+k]
        else:
            break
    ans = max(ans,(Alen-i-1+cnt))

print(ans)

Measured memory_bytes: 41200
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
int mod=int(1e9)+7;
int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    int n;
    cin>>n;
    int a[n+1][3];
    for(int i=1;i<=n;i++){
        for(int j=0;j<3;j++){
            cin>>a[i][j];
        }
    }
    ll dp[n+1][3];
    memset(dp,0,sizeof(dp));
    dp[1][0]=a[1][0];
    dp[1][1]=a[1][1];
    dp[1][2]=a[1][2];
    for(int i=2;i<=n;i++){
        dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a[i][0];
        dp[i][1]=max(dp[i-1][0],dp[i-1][2])+a[i][1];
        dp[i][2]=max(dp[i-1][1],dp[i-1][0])+a[i][2];
    }
    cout<<max({dp[n][0],dp[n][1],dp[n][2]})<<"\n";
}

Measured memory_bytes: 7112
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

typedef long long ll;

#define INF 1000000009LL
#define MOD 1000000007LL

ll dp[1005][1005];
int H, W;
char board[1000][1000];

int main() {
  int H, W; cin >> H >> W;
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      cin >> board[i][j];
    }
  }
  
  dp[0][1] = 1LL;
  for (int h = 0; h < H; h++) {
    for (int w = 0; w < W; w++) {
      if (board[h][w] == '.') dp[h+1][w+1] = (dp[h][w+1] + dp[h+1][w]) % MOD;
    }
  }
  
  cout << dp[H][W] << endl;
  return 0;
}



Measured memory_bytes: 9088
#include <stdio.h>
int main(){
  int a,b,c;
  int cnt=0;
  scanf("%d %d %d",&a,&b,&c);

  for(int i = a ;i <= b ; i++){
    if(c%i==0){
      cnt++;
    }
  }
  printf("%d\n",cnt);
}



Measured memory_bytes: 2144
#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
  int n;
  cin >> n;
  vector<int> v;
  for (int i = 0; i < n; ++i) {
    int a;
    cin >> a;
    v.push_back(a);
  }
  
  long long sum = 0;
  for (int i = 0; i < n - 1; ++i) {
    for (int j = i + 1; j < n; ++j) {
      sum += (v[i] * v[j]);
    }
  }
  cout << sum << endl;
}

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

public class Main {

	public static String Y = "Yes";
	public static String N = "No";
	public static long MOD = (long) (Math.pow(10, 9) + 7);
	public static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {

		int a = ni();
		out(a + a * a + a * a * a);

	}

	/*
	 * 以下メソッド集
	 */
	static int[] sort(int[] n) {
		Arrays.sort(n);
		return n;
	}

	static long[] sort(long[] n) {
		Arrays.sort(n);
		return n;
	}

	static int ketasuu(int n) {
		String str = "" + n;
		return str.length();
	}

	static int account(String str) {
		String target = "AC";
		int count = 0;
		int len = str.length();
		for (int i = 0; i < len - 1; i++) {
			if (target.equals(str.substring(i, i + target.length()))) {
				count++;
			}
		}
		return count;
	}

	static int ni() {
		return sc.nextInt();
	}

	static long nl() {
		return sc.nextLong();
	}

	static double nd() {
		return sc.nextDouble();
	}

	static String n() {
		return sc.next();
	}

	static char[] nc() {
		return sc.next().toCharArray();
	}

	static int kaijo(int n) {
		if (n == 0 || n == 1) {
			return 1;
		} else {
			return n * kaijo(n - 1);
		}
	}

	static int fib(int n) {
		return (n == 1 || n == 0) ? n : fib(n - 2) + fib(n - 1);
	}

	static long lcm(long m, long n) {

		return m * n / gcd(m, n);
	}

	static int lcm(int m, int n) {

		return m * n / gcd(m, n);
	}

	static long gcd(long a, long b) {
		return (b == 0) ? a : gcd(b, a % b);
	}

	static int gcd(int a, int b) {
		return (b == 0) ? a : gcd(b, a % b);
	}

	static void out(String info) {
		System.out.println(info);
	}

	static void out(int info) {
		System.out.println(info);
	}

	static void out(double info) {
		System.out.println(info);
	}

	static void out(long info) {
		System.out.println(info);
	}

	static void out(char info) {
		System.out.println(info);
	}

	static void out(Object obj) {
		System.out.println(obj.toString());
	}

	static void outn(String info) {
		System.out.print(info);
	}

	static void outn(int info) {
		System.out.print(info);
	}

	static void outn(double info) {
		System.out.print(info);
	}

	static void outn(long info) {
		System.out.print(info);
	}

	static void outn(char info) {
		System.out.print(info);
	}

	static double max(double d, double e) {
		return Math.max(d, e);
	}

	static long max(long a, long b) {
		return Math.max(a, b);
	}

	static long min(long d, long e) {
		return Math.min(d, e);
	}

	static int min(int a, int b) {
		return (int) Math.min(a, b);
	}
}

class XY {
	int h;
	int c;

	XY(int h, int c) {
		this.h = h;
		this.c = c;
	}
}


Measured memory_bytes: 35756
#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    int N;
    cin >> N;
    long A[100000];
    long sum = 0;
    for(int i = 0; i < N; i++){
        cin >> A[i];
    }
    sort(A, A+N);
    for(int i = 0; i < N; i++){
        sum += A[i];
    }
    for(int i = N-1; i >= 0; i--){
        sum -= A[i];
        if(2*sum < A[i]){
            cout << N-i << endl;
            break;
        }
    }
}

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

using namespace std;

using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
constexpr ld EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr int MOD = 1e9 + 7;

template <typename T>
void printv(const vector<T> &v)
{
    int sz = v.size();
    for (int i = 0; i < sz; i++)
    {
        cout << v[i] << " \n"[i == sz - 1];
    }
}

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

    ll K, N;
    cin >> N >> K;
    vector<ll> t(N), d(N);
    priority_queue<P> que;
    for (int i = 0; i < N; i++)
    {
        cin >> t[i] >> d[i];
        t[i]--;
        que.push(P(d[i], t[i]));
    }
    ll res = 0, var = 0, sum = 0;
    vector<int> used(N, 0);
    priority_queue<ll, vector<ll>, greater<ll>> amari;
    for (int i = 0; i < K; i++)
    {
        P p = que.top();
        que.pop();
        sum += p.first;
        if (used[p.second])
        {
            amari.push(p.first);
        }
        else
        {
            var++;
            used[p.second] = 1;
        }
    }
    res = sum + var * var;
    while (!que.empty())
    {
        P p = que.top();
        que.pop();
        if (used[p.second])
            continue;
        if (amari.empty())
            continue;
        sum -= amari.top();
        sum += p.first;
        amari.pop();
        var++;
        used[p.second] = 1;
        res = max(res, sum + var * var);
    }
    cout << res << endl;
}


Measured memory_bytes: 4592
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int M=2010,E=20005;
const ll inf=-1000000000000000000ll;
int n,m,et,s,z0,z1,z2,z3,t,x,y,z;
ll ans;
int fi[M],pv[M],pe[M],mw[M],in[M],qu[M],qh,qt;
ll d[M];
struct edge{int v,w1,w2,n;}e[E];
void add(int v,int u,int w1,int w2){
//	printf("%d %d %d %d\n",v,u,w1,w2);
	e[et]=(edge){u,w1,w2,fi[v]};fi[v]=et++;
	e[et]=(edge){v,0,-w2,fi[u]};fi[u]=et++;
}
void pau(){
	int tim=time(0)+2;
	while(time(0)<tim);
}
bool bfs(){
//	printf("\n\n\n");
	for(int i=1;i<=m;i++)d[i]=inf;
	d[s]=0;mw[s]=E;
	qu[1]=s;qh=1;qt=1;
	while(qh<=qt){
		int v=qu[(qh++)%M];
		in[v]=0;//printf("v=%d\n",v);
		for(int i=fi[v];i!=-1;i=e[i].n){
			int u=e[i].v;ll w=d[v]+e[i].w2;
//			printf("u=%d w=%lld i=%d\n",u,w,i);
//			pau();
			if(e[i].w1!=0&&w>d[u]){
				d [u]=w;
				pv[u]=v;
				pe[u]=i;
				mw[u]=min(mw[v],e[i].w1);
				if(in[u]==0){in[u]=1;qu[(++qt)%M]=u;}
			}
		}
	}
//	printf("m=%d\n",m);
//	for(int i=1;i<=m;i++)printf("%lld ",d[i]);printf("\n");
	return d[t]!=inf;
}
void upd(){
//	printf("\n\n\nFindPath\n\n");
	ll tw=0ll;int tm=mw[t];
	for(int i=t;i!=s;i=pv[i]){
//		printf("i=%d\n",i);
		tw+=e[pe[i]].w2;
		e[pe[i]  ].w1-=tm;
		e[pe[i]^1].w1+=tm;
	}
//	printf("tw=%lld tm=%d\n",tw,tm);
	ans+=tw*tm;
}
int main(){
//	freopen("3.in","r",stdin);
	memset(fi,-1,sizeof(fi));
	scanf("%d",&n);m=n<<1;
	s =++m;
	t =++m;
	z0=++m;
	z1=++m;
	z2=++m;
	z3=++m;
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&x,&y,&z);
		add(s,i ,z,   0);
		add(i,z0,E, x+y);
		add(i,z1,E, x-y);
		add(i,z2,E,-x+y);
		add(i,z3,E,-x-y);
	}
	for(int i=n+1;i<=n<<1;i++){
		scanf("%d%d%d",&x,&y,&z);
		add(i ,t,z,   0);
		add(z3,i,E, x+y);
		add(z2,i,E, x-y);
		add(z1,i,E,-x+y);
		add(z0,i,E,-x-y);
	}
	while(bfs())upd();
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,(n)-1,0)
#define all(v) v.begin(), v.end()
#define endk '\n'
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;
const ld eps = 1e-10;
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b){if(a>b) a=b;}
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b){if(a<b) a=b;}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n; cin >> n;
  vector<ll> A(n), B(n), C(n);
  rep(i, n) cin >> A[i];
  rep(i, n) cin >> B[i];
  rep(i, n) cin >> C[i];
  sort(all(A));
  sort(all(B));
  sort(all(C));
  vector<ll> cnt(n);
  rep(i, n) cnt[i] = end(C) - lower_bound(all(C), B[i]+1);
  rrep(i, n) if(i) cnt[i-1] += cnt[i];
  ll ans = 0;
  rep(i, n) ans += cnt[lower_bound(all(B), A[i]+1) - begin(B)];
  cout << ans << endk;
  return 0;
}


Measured memory_bytes: 6364
import java.io.BufferedReader; 
import java.io.IOException; 
import java.io.InputStreamReader; 
public class Main  
{ 
    public static void main(String[] args) throws IOException  
    { 
        //Enter data using BufferReader 
        BufferedReader reader =  
                   new BufferedReader(new InputStreamReader(System.in)); 
         
        // Reading data using readLine 
        String input = reader.readLine(); 
      	int n = Integer.valueOf(input);
      	int res = n % 2 == 0 ? n / 2 : n /2 + 1;
  
        // Printing the read line 
        System.out.println(res);         
    } 
} 

Measured memory_bytes: 22996
using System;
using System.Linq;

class C
{
	static void Main()
	{
		var x = int.Parse(Console.ReadLine());
		Console.WriteLine(GetPrimes(100003).First(p => p >= x));
	}

	static int[] GetPrimes(int n)
	{
		var b = new bool[n + 1];
		for (int p = 2; p * p <= n; ++p) if (!b[p]) for (int x = p * p; x <= n; x += p) b[x] = true;
		return Enumerable.Range(2, n - 1).Where(x => !b[x]).ToArray();
	}
}


Measured memory_bytes: 13408