akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
import java.lang.*;


public class Main {
    static String s;
    static String t;
    static int sl;
    static int tl;
    static int[][] lcs;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        s = sc.next();
        t = sc.next();
        sl = s.length();
        tl = t.length();
        lcs = new int[sl + 1][tl + 1];
        for (int i = 1; i <= sl; i++) {
            for (int j = 1; j <= tl; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    lcs[i][j] = lcs[i - 1][j - 1] + 1;
                } else {
                    lcs[i][j] = Math.max(lcs[i - 1][j], lcs[i][j - 1]);
                }
            }
        }
        plcs(sl, tl);
        System.out.println(sb.reverse());
    }
    static void plcs(int i, int j) {
        if (i == 0 || j == 0) {
            return;
        }
        if (s.charAt(i - 1) == t.charAt(j - 1)) {
            sb.append(s.charAt(i - 1));
            plcs(i - 1, j - 1);
        } else {
            if (lcs[i][j - 1] > lcs[i - 1][j]) {
                plcs(i, j - 1);
            } else {
                plcs(i - 1, j);
            }
        }
    }
}

Measured memory_bytes: 82900
#include<iostream>
#include<algorithm>
using namespace std;
bool min(int *p);
int main(){
    int n;
    int *p;
    int count=0;
    int i;
    cin >> n;
    p = new int[n];
    
    for(i=0;i<n;i++){
        cin >> p[i];
    }
    for(i=0;i<n-2;i++){
        if( (p[i] <= p[i+1] && p[i+1] <= p[i+2]) ||
            (p[i] >= p[i+1] && p[i+1] >= p[i+2])){
            count++;
        }
    }
    cout << count << endl;
    
    return 0;
}


Measured memory_bytes: 256
//Zory-2019
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pr pair<int,int>
#define FR first
#define SE second
#define MP make_pair
#define PB push_back
#define vc vector
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define bin(x) (1ll<<(x))
#define fo(i,l,r) for(int i=(l),I=(r);i<=I;i++)
#define fd(i,r,l) for(int i=(r),I=(l);i>=I;i--)
namespace mine
{
    ll qread()
    {
        ll ans=0,f=1;char c=getchar();
        while(c<'0' or c>'9') {if(c=='-')f=-1;c=getchar();}
        while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
        return ans*f;
    }
    void write(ll num){if(num<0) putchar('-'),num=-num;if(num>=10) write(num/10);putchar('0'+num%10);}
    void write1(ll num){write(num);putchar(' ');}
    void write2(ll num){write(num);putchar('\n');}
    template<typename T> void chmax(T &x,const T y) {x=(x>y?x:y);}
    template<typename T> void chmin(T &x,const T y) {x=(x<y?x:y);}
    ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}

    const int INF=0x3f3f3f3f;
    const int MOD=1e9+7;
    int mm(const int x){return x>=MOD?x-MOD:x;}
    template<typename T> void add(T &x,const int &y){x=(x+y>=MOD?x+y-MOD:x+y);}
    ll qpower(ll x,ll e,int mod=MOD){ll ans=1;while(e){if(e&1)ans=ans*x%mod;x=x*x%mod;e>>=1;}return ans;}
    ll invm(ll x){return qpower(x,MOD-2);}
    const int N=1e7+10;


    void main()
	{
        int n=qread();ll sum=0,ans=-1;fo(i,1,n){ll x=qread(),y=qread();sum+=x*y;ans+=y;}
        ans+=(sum-1)/9;write(ans);
	}
};//(ans+MOD)%MOD
signed main()
{
    srand(time(0));
    mine::main();
}


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

int main() {
    int h, w;
    cin >> h >> w;
    int grid[h][w];
    rep(i, h) {
        rep(j, w) {
            cin >> grid[i][j];
        }
    }
    rep(i, h) {
        rep(j, w) {
            int b;
            cin >> b;
            grid[i][j] -= b;
            if (grid[i][j] < 0) grid[i][j] = -grid[i][j];
        }
    }
    bool dp[h][w][(h + w) * 80]{};
    dp[0][0][abs(grid[0][0])] = true;
    rep(i, h) {
        rep(j, w) {
            rep(k, (h + w) * 80) {
                if (i - 1 >= 0) {
                    dp[i][j][k] |= dp[i - 1][j][abs(k - grid[i][j])];
                    dp[i][j][k] |= dp[i - 1][j][k + abs(grid[i][j])];
                }
                if (j - 1 >= 0) {
                    dp[i][j][k] |= dp[i][j - 1][abs(k - grid[i][j])];
                    dp[i][j][k] |= dp[i][j - 1][k + abs(grid[i][j])];
                }
            }
        }
    }
    for (int i = 0; i <= (h + w) * 80; i++) {
        if (dp[h - 1][w - 1][i]) {
            cout << i << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 80256
# Problem A - ><

# input
S = input()

# initialization
N = len(S) + 1
num_list = [0]*N
ans = 0

# count
for i in range(N-1):
    if S[i]=='<':
        num_list[i+1] = num_list[i] + 1

for i in range(N-2, -1, -1):
    if S[i]=='>':
        num_list[i] = max(num_list[i], num_list[i+1]+1)

# output
ans = sum(num_list)
print(ans)


Measured memory_bytes: 23336
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <cmath>
#include <cstdio>

using namespace std;

typedef long long ll;

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

int main(int argc, char **argv)
{
    int N;
    cin >> N;
    ll A[N + 1], B[N];
    REP(i, N + 1) cin >> A[i];
    REP(i, N) cin >> B[i];

    ll c = 0;
    REP(i, N) {
        if (A[i] <= B[i]) {
            c += A[i];
            B[i] -= A[i];
            A[i] = 0;
            if (A[i + 1] <= B[i]) {
                c += A[i + 1];
                A[i + 1] = 0;
            }
            else {
                c += B[i];
                A[i + 1] -= B[i];
            }
        }
        else {
            c += B[i];
            A[i] -= B[i];
        }
    }
    cout << c << endl;
    return 0;
}


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

#define FOR(s, i, n) for(int i = s; i n; i++)
typedef long long ll;
const int INF = 1e9;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n;
	cin>>n;
	string temp;
	set<string> s;
	FOR(0, i, <n){
		cin>>temp;
		s.insert(temp);
	}
	cout<<s.size()<<'\n';
	return 0;
}

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

int main(){
    int A, B, C, D;
    cin >> A >> B >> C >> D;
    int L = A + B;
    int R = C + D;
    if(L > R){
        cout << "Left" << endl;
    }else if(L == R){
        cout << "Balanced" << endl;
    }else{
        cout << "Right" << endl;
    }
}

Measured memory_bytes: 3616
import math
while True:
    n = int(input())
    if n == 0:
        break
    students = list(map(int,input().split()))
    sum_s = sum(students)
    ave = sum_s/n
    bun = 0
    for s in students:
        bun += (ave - s) ** 2
    bun /= n

    print(math.sqrt(bun))


Measured memory_bytes: 5696
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
  int a[4];
int main(){
  int n,a,b,c,d;
  cin >> n;
  d = n%10;
  c = (n/10)%10;
  b = (n/100)%10;
  a = n/1000;
  char op1,op2,op3;
  for(int tmp = 0; tmp < 8; tmp++){
    bitset<8>B(tmp);
    int sum = a;
    if(B.test(0)) {
      sum += b; op1 = '+';
    }
    if(!B.test(0)) {
      sum -= b; op1 = '-';
    }
    if(B.test(1)) {
      sum += c; op2 = '+';
      }
    if(!B.test(1)) {
      sum -= c; op2 = '-';
    }
    if(B.test(2)) {
      sum += d; op3 = '+';
    }
    if(!B.test(2)) {
      sum -= d; op3 = '-';
    }
    if(sum == 7){
      cout << a << op1 << b << op2 << c << op3 << d << "=7" << endl;
      break;
    }
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define yes { cout << "YES" << endl; exit(0); }
#define no { cout << "NO" << endl; exit(0); }
#define impossible { cout << "Impossible" << endl; exit(0); }

using namespace std;

typedef long long ll;
typedef pair<int,int> Pair;

const int Nmax = 1e7 + 5, Mod = 998244353;

int n;
int doi[Nmax], fact[Nmax], ifact[Nmax];

static int inm(int x, int y)
{
    return (ll) x * y % Mod;
}

void add_to(int &x, int y)
{
    x += y; if(x >= Mod) x -= Mod;
}

void inm_to(int &x, int y)
{
    x = (ll) x * y % Mod;
}

static int comb(int n, int k)
{
    return inm( fact[n], inm(ifact[k], ifact[n-k]) );
}

int power(int a, int b)
{
    int ans = 1;
    while(b)
    {
        if(b&1) inm_to(ans, a);
        b >>= 1;
        inm_to(a, a);
    }
    return ans;
}

int main()
{
    //freopen("inputC", "r", stdin);
    // freopen("output", "w", stdout);
    cin.sync_with_stdio(false); cin.tie(0);

    cin >> n;

    int i;
    int ans = 1;
    
    doi[0] = 1; fact[0] = 1; ifact[0] = 1;
    for(i=1; i<=n; ++i) inm_to(ans, 3), doi[i] = inm(doi[i-1], 2), fact[i] = inm(fact[i-1], i);

    ifact[n] = power(fact[n], Mod-2);
    for(i=n-1; i; --i) ifact[i] = inm(ifact[i+1], i+1);

    int wrong = 0;
    for(i=n/2+1; i<=n; ++i)
        add_to( wrong, inm (comb(n, i), doi[n-i] ) );
    
    inm_to(wrong, 2);
    add_to(ans, Mod - wrong);

    cout << ans << '\n';

    return 0;
}



Measured memory_bytes: 117504
#include<cstdio>
#include<iostream>
#include<vector>
#include<tuple>
#include<queue>
#include<algorithm>
#include<string.h>

using namespace std;
typedef pair<int,int> P;
const int inf=10000000;

int h,w;
char s[51][51];

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

int d[51][51];

int bfs(){
  queue<P>que;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      d[i][j]=inf;
    }
  }
  que.push(P(0,0));
  d[0][0]=0;
  while(que.size()){
    P p=que.front();
    que.pop();
    if(p.first==h-1 && p.second==w-1)break;
    for(int i=0;i<4;i++){
      int nx=p.first+dx[i];
      int ny=p.second+dy[i];
      if(0<=nx&&nx<h&&0<=ny&&ny<w&&d[nx][ny]==inf&&s[nx][ny]!='#'){
        que.push(P(nx,ny));
        d[nx][ny]=d[p.first][p.second]+1;
      }
    }
  }
  return d[h-1][w-1];
}



int main(int argc, char* argv[]){
  int white=0;
  scanf("%d%d",&h,&w);
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      scanf(" %c",&s[i][j]);
      if(s[i][j]=='.')white++;
    }
  }
  int ans = bfs();
  /*for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      printf("%c",s[i][j]);
    }
    printf("\n");
  }*/
  //printf("%d\n",white);
  //printf("%d\n",ans);
  if(ans==inf)puts("-1");
  else{
    printf("%d\n",white-(ans+1));
  }
  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] V = new int[N];
        int[] C = new int[N];
        for (int i=0; i<N; i++) {
            V[i] = sc.nextInt();
        }
        for (int i=0; i<N; i++) {
            C[i] = sc.nextInt();
        }
        int cnt = 0;
        for (int i=0; i<N; i++) {
            if (V[i] - C[i] > 0)
                cnt += V[i] - C[i];
        }
        System.out.println(cnt);
    }
}


Measured memory_bytes: 22996
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = pow(10, 9) + 7;
//const ll MOD = 998244353;
//const ll MOD = ;
ll mod(ll A, ll M) {return (A % M + M) % M;}
const ll INF = 1LL << 60;
template<class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
ll divceil(ll A, ll B) {return (A + (B - 1)) / B;}
ll myctoi(char C) {return C - '0';}
char myitoc(ll N) {return '0' + N;}
#define FINALANS(A) {cout << (A) << endl; exit(0);}

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

  ll ans = 0, x = 0;
  for (ll i = 0; i < N - 1; i++)
  {
    if (H.at(i + 1) <= H.at(i))
      x++;
    else
      x = 0;
    chmax(ans, x);
  }
  cout << ans << endl;
}

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

#define int long long
#define INT int
#define MOD 1000000007

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(i) (i).begin(), (i).end()
#define rall(i) (i).begin(), (i).end(), greater<int>()
#define elif else if
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fst first
#define sec second
template <typename T>
void print(T x)
{
    std::cout << x << '\n';
}
typedef long long ll;
const long long INF = 1LL << 60;

/* nの約数を求める関数*/
vector<int> enum_div(int n) //nの約数を列挙
{
    vector<int> divisor;
    for (int i = 1; i * i <= n; ++i)
    {
        if (n % i == 0)
        {
            if (i != 1)
                divisor.push_back(i);
            if (i != 1 && i * i != n)
            {
                divisor.push_back(n / i);
            }
        }
    }
    return divisor;
}

/* xとyの最大公約数を求める関数*/
int gcd(int x, int y)
{
    int temp;
    while (y != 0)
    {
        temp = y;
        y = x % y;
        x = temp;
    }
    return (x);
}

signed main()
{

    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n)
    {
        cin >> a[i];
    }

    sort(rall(a));

    int g = a[0];
    rep(i, n)
    {
        g = gcd(g, a[i]);
    }
    if (g > 1)
    {
        cout << "not coprime" << endl;
        return 0;
    }

    unordered_map<int, int> indx;
    rep(i, n)
    {
        if (indx[a[i]] > 0)
        {
            cout << "setwise coprime" << endl;
            return 0;
        }
        vector<int> temp = enum_div(a[i]);
        for (auto x : temp)
        {
            indx[x]++;
            if (indx[x] > 1)
            {
                cout << "setwise coprime" << endl;
                return 0;
            }
        }
    }

    cout << "pairwise coprime" << endl;

    return 0;
}


Measured memory_bytes: 11144
#include <iostream>
#include <array>

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

    long long int n;

    std::array<int, 130> age2generation;

    int i;
    for (i = 0; i < 10; ++i) {
        age2generation[i] = 0;
    }
    for (i = 10; i < 20; ++i) {
        age2generation[i] = 1;
    }
    for (i = 20; i < 30; ++i) {
        age2generation[i] = 2;
    }
    for (i = 30; i < 40; ++i) {
        age2generation[i] = 3;
    }
    for (i = 40; i < 50; ++i) {
        age2generation[i] = 4;
    }
    for (i = 50; i < 60; ++i) {
        age2generation[i] = 5;
    }
    for (int i = 60; i < 130; ++i) {
        age2generation[i] = 6;
    }

    while (std::cin >> n, n) {
        
        std::array<long long int, 7> arr{{}};
        int age;

        for (; n--;) {
            std::cin >> age;
            ++arr[age2generation[age]];
        }
        
        for (const auto& cnt : arr) {
            std::cout << cnt << std::endl;
        }
    }

    return 0;
}

Measured memory_bytes: 1200
#include<stdio.h>
int main(void){
  int l,i;
  scanf("%d",&l);
  char a[l],b[l];
  scanf("%s",a);
  scanf("%s",b);
  for(i=0;i<l;i++){
    printf("%c",a[i]);
    printf("%c",b[i]);
  }
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int,int>
#define ff first
#define ss second
#define boost ios::sync_with_stdio(false);cin.tie(nullptr)
#define endl "\n"
#include "string"


int32_t main(){
	boost;
	int n;
	cin >> n;
	if(n % 2 == 0) {
		cout << -1 << endl;
		return 0;
	}
	int cur = 7, cnt = 1;
	while(cnt <= n) {
		if(cur % n == 0) {
			cout << cnt << endl;
			return 0;
		}
		cnt++;
		cur = (cur * 10 + 7) % n;
	}
	cout << -1 << endl;
}


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

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<ll, int> pr;

#define MAX (ll)(1e5)
#define INF (1ll<<60)

struct edge{
	int to;
	ll cost;
};

int n, m;
vector<edge> yen[MAX+1], snk[MAX+1];
ll cost_y[MAX+1], cost_s[MAX+1];

void dijkstra(int s, vector<edge> g[], ll d[]){
	priority_queue<pr, vector<pr>, greater<pr>> que;
	fill(d, d+n+1, INF);
	d[s]=0;
	que.push(pr(0, s));

	while(!que.empty()){
		pr 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(pr(d[e.to], e.to));
			}
		}
	}
	return;
}

int main(){
	int s, t;
	cin >> n >> m >> s >> t;
	for(int i=0; i<m; i++){
		int u, v;
		ll a, b;
		cin >> u >> v >> a >> b;
		yen[u].push_back(edge{v, a});
		yen[v].push_back(edge{u, a});
		snk[u].push_back(edge{v, b});
		snk[v].push_back(edge{u, b});
	}

	dijkstra(s, yen, cost_y);
	dijkstra(t, snk, cost_s);

	vector<ll> ans(n+1);
	ll m_cost=INF;
	for(int i=n; i>0; i--){
		m_cost=min(m_cost, cost_y[i]+cost_s[i]);
		ans[i]=(ll)(1e15)-m_cost;
	}
	for(int i=1; i<=n; i++) cout << ans[i] << endl;
	return 0;
}

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

int main() {
    int a, b, c, k;
    cin >> a >> b >> c >> k;
    int ans = 0;
    if (k <= a) ans += k;
    else {
        ans += a;
        if (k <= a + b) ans += 0;
        else {
            ans -= k-(a+b);
        }
    }
    cout<< ans << endl;
    return 0;
}

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

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

const int mx=1e6+11;
const double PI = acos(-1);
#define MOD 1000000007


#define nl '\n'
#define pb push_back
#define F first
#define S second
#define I insert
#define mp make_pair

#define sz(x) x.size()
#define tt int t; cin>>t; while(t--)
#define lo(i,a,b) for(int i=a;i<b;i++)
#define be(a) (a).begin(),(a).end()
#define rbe(a) (a).rbegin(),(a).rend()
#define mem(a,b) memset(a,b,sizeof(a))

#define su ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define frac cout.unsetf(ios::floatfield); cout.precision(10); cout.setf(ios::fixed,ios::floatfield);

#define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0)
void faltu () {            cerr << endl;}
template < typename T, typename ... hello>void faltu( T arg, const hello &... rest) {cerr << arg << ' ';faltu(rest...);}


int main()
{
   su;
   int H,W,h,w;
   cin>>H>>W>>h>>w;
   cout<<(H-h)*(W-w)<<nl;
   return 0;
}


Measured memory_bytes: 3644
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

using namespace std;
using ll = long long;

constexpr ll infl = 10000000000000007LL;
constexpr int inf = 1000000007;

int main() {
    int n, ma, mb;
    cin >> n >> ma >> mb;
    vector<int> c(n), d(n);
    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b >> c[i];
        d[i] = mb * a - ma * b;
    }

    vector<vector<int>> dp(n, vector<int>(7201, inf));
    dp[0][d[0] + 3600] = c[0];
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j <= 7200; ++j) {
            dp[i][j] = dp[i - 1][j];
            if (j == d[i] + 3600)
                dp[i][j] = min(dp[i][j], c[i]);
            if (j - d[i] >= 0)
                dp[i][j] = min(dp[i][j], dp[i - 1][j - d[i]] + c[i]);
        }
    }

    if (dp.back()[3600] <= 4000)
        cout << dp.back()[3600] << endl;
    else
        cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 1408
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int lld;

const lld mod = 1e9+7;
const lld INF = 1e9;
//const lld MAXN = 1e9;

struct node
{
	int num,x,y;
};

int main()
{
	int h,w,d;
	cin >> h >> w >> d;
	vector<vector<lld> > a(h,vector<lld>(w,0));
	for(int i = 0; i < h; i++)
	{
		for(int j = 0; j < w; j++)
		{
			cin >> a[i][j];
		}
	}
	lld q;
	cin >> q;
	vector<pair<int,int> > lr(q);
	for(int i = 0; i < q; i++)
	{
		cin >> lr[i].first >> lr[i].second;
	}

	vector<node> p(h*w);
	for(int i = 0; i < h; i++)
	{
		for(int j = 0; j < w; j++)
		{
			p[a[i][j]-1].num = a[i][j];
			p[a[i][j]-1].x = j;
			p[a[i][j]-1].y = i;
		}
	}

	vector<lld> dist(h*w);
	for(int i = 0; i < h*w; i++)
	{
		if (p[i].num <= d)
		{
			dist[i] = 0;
		}else
		{
			dist[i] = dist [i-d] + abs(p[i].x - p[i-d].x) + abs(p[i].y - p[i-d].y);
		}
	}

	// for(int i = 0; i < h*w; i++)
	// {
	// 	cout << i+1 << "  " << dist[i] << endl;
	// }

	for(int i = 0; i < q; i++)
	{
		cout << dist[lr[i].second-1] - dist[lr[i].first-1] << endl;
	}

	return 0;
}

Measured memory_bytes: 4352
#include <iostream>
#include <vector>
#include <bitset>
#include <string>
#include <array>
#include <random>
#include <chrono>
#include <algorithm>

int main(void){
	int64_t w, h, x, y;
	std::cin >> w >> h >> x >> y;
	std::cout << double(w * h) / 2 << " " << (x * 2 == w && y * 2 == h) << std::endl;
	return 0;
}


Measured memory_bytes: 256
use proconio::input;

fn main() {
    input! {
        n: usize,
        ab: [(i64, i64); n],
    };
    let mut a = ab.iter().map(|&(a_i, _)| a_i).collect::<Vec<_>>();
    let mut b = ab.iter().map(|&(_, b_i)| b_i).collect::<Vec<_>>();
    a.sort();
    b.sort();
    let ans = if n % 2 == 0 {
        let lx2 = a[n / 2 - 1] + a[n / 2];
        let rx2 = b[n / 2 - 1] + b[n / 2];
        rx2 - lx2 + 1
    } else {
        let l = a[n / 2];
        let r = b[n / 2];
        r - l + 1
    };
    println!("{}", ans);
}


Measured memory_bytes: 12936
#include <bits/stdc++.h>
typedef long long int lli;
using namespace std;
/* The important thing is that if your current position is
 * greater than n - k - 1, then directly jump to the last
 * position (Can be proved by simple geometry, draw a line
 * joining the first point and the last point, and the difference
 * of all k/less jumps will always be greater than or equal to the
 * difference between the current element and the last element)
 * */
int fn(vector<int>& h, int n, int i, int k, vector<int>& t){
	int cost = INT_MAX;
	if(i == n - 1){
		return 0;
	}

	if(t[i] != -1){
		return t[i];
	}

	if(i >= n - k - 1){
		cost = abs(h[n - 1] - h[i]);
		t[i] = cost;
		return t[i];
	}

	for(int j = 0; j < k; j++){
		cost = min(cost, abs(h[i + j + 1] - h[i]) + fn(h, n, i + j + 1, k, t));
		t[i] = cost;
	}

	return t[i];
}
int main(){
	int n, k;
	cin >> n >> k;

	vector<int> h(n + 1), t(n + 1, -1);

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

	if(k >= n){
		cout << abs(h[0] - h[n - 1]) << "\n";
	}
	else{
		cout << fn(h, n, 0, k, t) << endl;
	}
}


Measured memory_bytes: 10368
#include <algorithm>
#include <bits/stdc++.h>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#define rep(X, Y) for (int(X) = 0; (X) < (Y); ++(X))
#define rrep(X, Y) for (int(X) = (Y)-1; (X) >= 0; --(X))
#define all(X) (X).begin(), (X).end()
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
#define print(x) cout << x << endl

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

bool isHateNum(long long N, vector<ll> D) {
  string str = to_string(N);
  for (char c : str) {
    for (ll n : D) {
      if (c - '0' == n) {
        return true;
      }
    }
  }
  return false;
}

void solve(long long N, long long K, std::vector<long long> D) {
  while (isHateNum(N, D)) {
    N++;
  }
  print(N);
  return;
}

int main() {
  long long N;
  scanf("%lld", &N);
  long long K;
  scanf("%lld", &K);
  std::vector<long long> D(K);
  for (int i = 0; i < K; i++) {
    scanf("%lld", &D[i]);
  }
  solve(N, K, std::move(D));
  return 0;
}


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

#define MOD 1000000007

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

    vector<int> S(N + 1);
    for (int i = 1; i <= N; i++)
    {
        cin >> S[i];
    }

    vector<int> T(M + 1);
    for (int i = 1; i <= M; i++)
    {
        cin >> T[i];
    }

    vector<vector<int>> dp(N + 1, vector<int>(M + 1, 0));
    for (int i = 1; i <= N; i++)
    {
        int sum = 0;
        for (int j = 1; j <= M; j++)
        {
            sum += dp[i - 1][j];
            sum %= MOD;
            if (S[i] == T[j])
            {
                dp[i][j] = sum + 1;
                dp[i][j] %= MOD;
            }
            else
            {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    int ans = 1;
    for (int x : dp[N])
    {
        ans += x;
        ans %= MOD;
    }
    cout << ans << endl;
}


Measured memory_bytes: 16000
import java.util.*;
import java.lang.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long mod = 1000000007;
		long[][][][] dp = new long[n + 1][4][4][4];//ACGT
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				for (int k = 0; k < 4; k++) {
					dp[3][i][j][k] = 1;
				}
			}
		}
		dp[3][0][2][1] = 0;
		dp[3][0][1][2] = 0;
		dp[3][2][0][1] = 0;
		for (int i = 4; i <= n; i++) {
			for (int j = 0; j < 4; j++) {
				for (int k = 0; k < 4; k++) {
					for (int l = 0; l < 4; l++) {
						for (int m = 0; m < 4; m++) {
							//?021, ?201, ?012, 0?21, 02?1
							if (!(k == 0 && l == 2 && m == 1) && !(k == 2 && l == 0 && m == 1) && !(k == 0 && l == 1 && m == 2) && !(j == 0 && l == 2 && m == 1) && !(j == 0 && k == 2 && m == 1)) {
								dp[i][k][l][m] += dp[i - 1][j][k][l];
								dp[i][k][l][m] %= mod;
							}
						}
					}
				}
			}
		}
		long ans = 0;
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				for (int k = 0; k < 4; k++) {
					ans += dp[n][i][j][k];
					ans %= mod;
				}
			}
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 22740
N, M = map(int, input().split())
xyz = [list(map(int,input().split())) for i in range(N)]

def lambdagen():
    for i in [-1,1]:
        for j in [-1,1]:
            for k in [-1,1]:
                yield lambda x:x[0]*i+x[1]*j+x[2]*k

ans = -10**20
gen = lambdagen()

for i in range(8):
    l = sorted(xyz, key=gen.__next__())
    x, y, z = 0, 0, 0
    for j in range(M):
        x += l[j][0]
        y += l[j][1]
        z += l[j][2]
    x, y, z = abs(x), abs(y), abs(z)
    ans = max(ans, x+y+z)
    # ans = max(ans, sum(l[:M]))

print(ans)
        

Measured memory_bytes: 3316
import heapq
n=int(input())
Ans=[]
A=[int(i) for i in input().split()]
A.sort()
if A[0]>=0:
  Ans=[]
  heapq.heapify(A)
  for i in range(n-2):
    a1=heapq.heappop(A)
    a2=heapq.heappop(A)
    Ans.append([a1,a2])
    heapq.heappush(A,a1-a2)
  a1=heapq.heappop(A)
  a2=heapq.heappop(A)
  Ans.append([a2,a1])
  print(a2-a1)
  for i in range(n-1):
    print(*Ans[i])

elif A[-1]<=0:
  Ans=[]
  AA=[]
  for i in range(n):
    AA.append(-A[i])
  heapq.heapify(AA)
  for i in range(n-2):
    a1=heapq.heappop(AA)
    a2=heapq.heappop(AA)
    Ans.append([-a1,-a2])
    heapq.heappush(AA,-(a2-a1))
  a1=heapq.heappop(AA)
  a2=heapq.heappop(AA)
  Ans.append([max(-a2,-a1),min(-a2,-a1)])
  print(max(-a2,-a1)-min(-a2,-a1))
  for i in range(n-1):
    print(*Ans[i])
else:    
  Ap,Az,Am=[],[],[]
  for i in range(n):
    if A[i]>0:
      Ap.append(A[i])
    elif A[i]==0:
      Az.append(A[i])
    else:
      Am.append(-A[i])
  Ap.sort()
  Am.sort()
  pp,mm=Ap.pop(),Am.pop()
  heapq.heapify(Ap)
  heapq.heapify(Am)

  while len(Am)>=1:
    am=heapq.heappop(Am)
    Ans.append([pp,-am])
    pp+=am
  while len(Ap)>=1:
    ap=heapq.heappop(Ap)
    Ans.append([-mm,ap])
    mm+=ap
  for i in range(len(Az)):
    Ans.append([pp,0])
  Ans.append([pp,-mm])
  print(pp+mm)
  for i in range(len(Ans)):
    print(*Ans[i])

Measured memory_bytes: 25768
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)     for(int i = 0; i < (int)(n); i++)
#define rep2(i, m, n) for(int i = m; i < (int)(n); i++)
#define MOD 1000000007

int main() {
  int N;
  cin >> N;
  
  vector<int64_t> Ai; 
  rep(i,N){
    int64_t tmpAi;
	cin >> tmpAi;
	Ai.push_back(tmpAi);  	
  }

  int64_t ans = 0;
  int64_t pow2n = 0;
  
  rep(i,61){
    int64_t zero = 0;
    int64_t one = 0;
    int64_t digitSum = 0;
    
    pow2n = i;
    
    rep(j,N){
      if((1LL << pow2n) & Ai.at(j)) one++;
	}
    zero = N - one;
    digitSum = (zero * one) % MOD;
	ans += digitSum * ((1LL << pow2n) % MOD);
    ans %= MOD;
  }
  
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 5360
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int t = sc.nextInt();
		int[] a = new int[n + 1];
		for(int i = 0 ; i < n ; i++) a[i] = sc.nextInt();
		long ans = 0;
		for(int i = 0 ; i < n ; i++) {
			if(i == n - 1) ans += t;
			else ans += Math.min(t, a[i + 1] - a[i]);
		}
		System.out.println(ans);
	}
}

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

int main() {

    int N, X;
    cin >> N >> X;

    int pos = 0;
    vector<int> L;
    int tmp;

    for (int i = 0; i < N; i++) {
        cin >> tmp;
        L.push_back(tmp);
    }

    for (int i = 0; i < N; i++) {
        pos += L[i];
        if (pos > X) {
            cout << i + 1 << endl;
            break;
        }
        if (i == N - 1) {
            cout << i + 2 << endl;
        }
    }

    return 0;
}


Measured memory_bytes: 256
card = []
for i in range(3):
    a1,a2,a3 = map(int,input().split())
    card.append([a1,a2,a3])

n = int(input())

for i in range(n):
    num = int(input())
    for j in [0,1,2]:
        for k in [0,1,2]:
         if num == card[j][k]:
             card[j][k] = 0
if card[0] == [0,0,0] or card[1] == [0,0,0] or card[2] == [0,0,0]:
    print('Yes')
elif [card[i][0] for i in range(3)] == [0,0,0] or [card[i][1] for i in range(3)] == [0,0,0] or [card[i][2] for i in range(3)] == [0,0,0]:
    print('Yes')
elif [card[0][0],card[1][1],card[2][2]] == [0,0,0] or [card[0][2],card[1][1],card[2][0]] == [0,0,0]:
    print('Yes')
else:
    print('No')


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

typedef long long ll;

ll N;
ll A[3000];
ll dp[3000 + 1][3000 + 1];

ll taro(ll i, ll j);
ll jiro(ll i, ll j);

ll taro(ll i, ll j) {
    // cout << "taro: " << i << " : " << j << endl;
    if (i > j) {
        return 0;
    }
    if (dp[i][j] != -1) {
        return dp[i][j];
    }

    dp[i][j] = max(A[i] + jiro(i + 1, j), A[j] + jiro(i, j - 1));

    return dp[i][j];
}

ll jiro(ll i, ll j) {
    // cout << "jiro: " << i << " : " << j << endl;
    if (i > j) {
        return 0;
    }

    return min(taro(i + 1, j) - A[i], taro(i, j - 1) - A[j]);
}

int main() {
    cin >> N;

    for (ll i = 0; i < N; i++) {
        ll a;
        cin >> a;
        A[i] = a;
    }

    for (ll i = 0; i < N; i++) {
        for (ll j = 0; j < N; j++) {
            dp[i][j] = -1;
        }
    }

    cout << taro(0, N - 1) << endl;
}

Measured memory_bytes: 70784
import math
import heapq
import sys
from collections import Counter
import numpy as np

#N,K=map(int, input[0].split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
#x=list(map(int, input[1].split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
#s = [input() for i in range(3)]

A,B=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき


K=(B**2-A**2)/((-2)*(A-B))

if K.is_integer():
    print(int(K))
else:
    print('IMPOSSIBLE')

Measured memory_bytes: 12492
#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast")
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int main(){
	int a,b,c;
	a=read();b=read();c=read();
	cout<<max(0,c-(a-b));
	puts("");
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main(){
	string s;
	int b,e;
	
	cin>>s;
	
	for(int i=0;i<s.size();i++){
		if(s[i] == 'A'){
			b=i;
			break;
		}
	}
	
	for(int j=s.size()-1; ;j--){
		if(s[j] == 'Z'){
			e=j;
			break;
		}
	}
	
	cout<<e-b+1<<endl;
	
	return 0;
}

Measured memory_bytes: 640
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {

        Scanner sc = new Scanner(System.in);
        
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int[] sum = {a + b, b + c, c + a};
        int min = Integer.MAX_VALUE;
        
        for(int i = 0; i < 3; i++){
            if(min > sum[i]) min = sum[i];
        }
        
        System.out.println(min);
    }
}


Measured memory_bytes: 23124
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;


int main() {
	int r, g, b,n;
	cin >> r >> g >> b>>n;
	int ans = 0;

	for (int i = 0; i<=n /r; i++) {
		for (int j = 0; j<=n /g ; j++) {
			int x = n - (r * i + g * j);
			if (x >= 0 && x % b == 0) {
				ans++;
			}
		}
	}

	cout << ans << endl;

		return 0;
}




Measured memory_bytes: 256
#include<cstdio>
#include<queue>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int n,a[N],b[N],pre[N],nxt[N]; long long ans; queue <int> q; bool vis[N];
inline bool check(CI id)
{
	return b[id]-a[id]>=b[pre[id]]+b[nxt[id]];
}
int main()
{
	RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
	for (i=1;i<=n;++i) scanf("%d",&b[i]),pre[i]=i-1,nxt[i]=i+1;
	for (nxt[pre[1]=n]=i=1;i<=n;++i) if (check(i)) q.push(i),vis[i]=1;
	while (!q.empty())
	{
		int nw=q.front(); vis[nw]=0; q.pop();
		int cur=(b[nw]-a[nw])/(b[pre[nw]]+b[nxt[nw]]);
		ans+=cur; b[nw]-=cur*(b[pre[nw]]+b[nxt[nw]]);
		if (!vis[pre[nw]]&&check(pre[nw])) q.push(pre[nw]),vis[pre[nw]]=1;
		if (!vis[nxt[nw]]&&check(nxt[nw])) q.push(nxt[nw]),vis[nxt[nw]]=1;
	}
	for (i=1;i<=n;++i) if (a[i]!=b[i]) return puts("-1"),0;
	return printf("%lld",ans),0;
}

Measured memory_bytes: 3968
import java.io.*;
import java.util.*;

public class Main{
  public static void main(String[] args)throws IOException{
    //BufferedReader br = new BufferedReader(System.in);
    Scanner sc = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);
    
    int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		
		if((a<c && c<b) || (b<c && c<a))
			out.println("Yes");
		else
			out.println("No");
    
    out.flush();
  }
}

Measured memory_bytes: 23252
def main():
    # 下、右、上、左
    dy = (1, 0, -1, 0)
    dx = (0, 1, 0, -1)
    H, W = map(int, input().split())
    s = ["." * (W + 2)]
    s += ["." + input() + "." for i in range(H)]
    s.append("." * (W + 2))
    for y in range(1, H + 1):
        for x in range(1, W + 1):
            if s[y][x] == "#" and\
                    "." == s[y + dy[0]][x + dx[0]]\
                    == s[y + dy[1]][x + dx[1]]\
                    == s[y + dy[2]][x + dx[2]]\
                    == s[y + dy[3]][x + dx[3]]:
                print("No")
                return
    print("Yes")
    return


main()


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define mx 111000
#define ll long long int
int main()
{
    ll a[100001],n,k,sum=0,i,j;
    cin >> n >> k;
    for(i=0;i<n;i++)
        cin>> a[i];
    sort(a,a+n);
    for(i=0;i<k;i++)
        sum+=a[i];
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 3640
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <functional>
#include <numeric>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>
#include <limits>
#include <iomanip>
#include <bitset>
#include <queue>
#include <unordered_set>

using namespace std;
typedef long long ll;

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
#define rep(i, n) for(int i = 0;i < n;i++)
const int INF = 1LL << 30;

int MOD = 1000000007;

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

    int n,d; cin >> n >> d;

    cout << (int)ceil(n/(2*d+1.0)) << endl;

    
    
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define EPS (1e-10)
#define equals(a,b) (fabs((a)-(b)) < EPS)
#define PI 3.141592653589793238
using namespace std;
#define int long long
struct Point{
  double x,y;
  Point(){}
  Point(double x,double y) :x(x),y(y){}
  Point operator + (Point p) {return Point(x+p.x,y+p.y);}
  Point operator - (Point p) {return Point(x-p.x,y-p.y);}
  Point operator * (double k) {return Point(x*k,y*k);}
  Point operator / (double k) {return Point(x/k,y/k);}
  double norm(){return x*x+y*y;}
  double abs(){return sqrt(norm());}

  bool operator < (const Point &p) const{
    return x!=p.x ? x < p.x : y < p.y;
  }

  bool operator == (const Point &p) const{
    return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS;
  }
};

typedef Point Vector;
typedef vector<Point> Polygon;

istream &operator >> (istream &is,Point &p){
  is>>p.x>>p.y;
  return is;
}

Vector spin(Vector v,double theta){
  Vector res;
  res.x=cos(theta)*v.x-sin(theta)*v.y;
  res.y=sin(theta)*v.x+cos(theta)*v.y;
  return res;
}
void koch(int n,Point p1,Point p2,Polygon&p){
  if(n==0){
    p.push_back(p1);
    return;
  }
  Vector v=(p2-p1)/3;
  Point p3=p1+v;
  Point p4=p3+spin(v,60*PI/180);
  Point p5=p1+v*2;
  koch(n-1,p1,p3,p);
  koch(n-1,p3,p4,p);
  koch(n-1,p4,p5,p);
  koch(n-1,p5,p2,p);
}
signed main(){
  int n;
  cin>>n;
  Polygon p;
  koch(n,Point(0,0),Point(100,0),p);
  p.push_back(Point(100,0));
  for(int i=0;i<(int)p.size();i++)
    printf("%.12f %.12f\n",p[i].x,p[i].y);
  return 0;
}

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

int main(){
  int n;
  cin >> n;
  map<long long,long long>mp;
  long long ans=0;
  for(int i=0;i<n;++i){
    long long a;
    cin >> a;
    ans+=mp[i-a];
    mp[i+a]++;
    //a[i]--;
  }

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


Measured memory_bytes: 26228
import java.util.*;

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

        for(int i = 1 ; i < N; i++){
            patarn = patarn * (K-1);
        }
        
        System.out.println(patarn);
    }
}

Measured memory_bytes: 21844
N=int(input())
a=list(map(int,input().split()))
cnt=[0]*9
ans=0
for score in a:
    if score <400: 
        cnt[0]+=1
    elif score <800: 
        cnt[1]+=1
    elif score<1200:
        cnt[2]+=1
    elif score<1600:
        cnt[3]+=1
    elif score<2000:
        cnt[4]+=1
    elif score<2400:
        cnt[5]+=1
    elif score<2800:
        cnt[6]+=1
    elif score<3200:
        cnt[7]+=1
    else:
        cnt[8]+=1
for i in cnt[:8:]:
    if i:
        ans+=1
print(max(1,ans),ans+cnt[8])

Measured memory_bytes: 9056
//https://atcoder.jp/contests/dp/tasks/dp_h
//H - Grid 1
#include <bits/stdc++.h>
#if LOCAL
#include "dump.hpp"
#else
#define dump(...)
#endif
using namespace std;
using ll=long long;
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
template<class T>bool chmax(T &a, const T &b) {if (a<b) { a=b; return 1; } return 0;}
template<class T>bool chmin(T &a, const T &b) {if (b<a) { a=b; return 1; } return 0;}
constexpr ll MOD=1e9+7;
int main() {
#if LOCAL&01
    std::ifstream in("./test/sample-1.in"); //input.txt
    std::cin.rdbuf(in.rdbuf());
#else
    cin.tie(0);
    ios::sync_with_stdio(false);
#endif
    ll H,W; cin>>H>>W;
    vector<string> awh(H);
    for(auto&& aw:awh){
        cin>>aw;
    }   
    vector<vector<ll>> dp(H,vector<ll>(W));
    auto get_val = [&](ll y,ll x)->ll{
        if (y<0||y>=H) return 0;
        if (x<0||x>=W) return 0;
        if (awh.at(y).at(x)=='#') return 0;
        return dp[y][x];
    };
    dp[0][0]=1;
    FOR(y,0,H){
        FOR(x,0,W){
            if (x==0&&y==0)continue; //FIXME:...
            dp[y][x]=(get_val(y,x-1)+get_val(y-1,x))%MOD;
        }
    }
    dump(dp);
    cout<<dp[H-1][W-1]<<endl;
    return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

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

#define DEBUG(x) cout<<#x<<": "<<x<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";REP(i, v.size())cout<<' '<<v[i];cout<<'\n'
#define ALL(a) (a).begin(), (a).end()

#define CHMIN(a, b) a=min((a), (b))
#define CHMAX(a, b) a=max((a), (b))

const ll MOD=1000000007ll;
// const ll MOD=998244353ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

const double EPS=1e-11;
#define EQ0(x) (abs((x))<EPS)
#define EQ(a, b) (abs((a)-(b))<EPS)

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	string s;
	int w;
	cin>>s>>w;
	REP(i, (s.size()-1)/w+1){
		cout<<s[i*w];
	}
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <cmath>
#include <cstdlib>
#include <climits>
using namespace std;

int main(){
  int a,b,c;
  cin >> a >> b >> c;
  int i = 1;

  for( int i = 1; i < b; i++){
    if(a*i % b == c){
      cout << "YES" << endl;
      return 0;
  }

    }

    cout << "NO" << endl;

    return 0;
}

Measured memory_bytes: 256
K, S = gets.split.map(&:to_i)

sum = 0
(0..K).each do |x|
    s = S - x
    next if s < 0
    if s <= K
        sum += s + 1
    elsif s <= 2*K
        sum += 2 * K - s + 1
    end
end

puts sum

Measured memory_bytes: 1788
#include <iostream>
#include <iomanip>
#include <vector>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <array>
#include <tuple>
#include <string>
#include <algorithm>
#include <functional> // greater など
#include <cmath>      // abs など
#include <numeric>    // accumulate, gcd など
#include <cassert>    // assert
#include <stdexcept>
#include <bitset>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for (int i = (a); i < (int)(b); i++)
typedef long long ll;

//////////////// //////////////// //////////////// //////////////// ////////////////
//////////////// //////////////// //////////////// //////////////// ////////////////

// constexpr inline ll mod = 1'000'000'007LL;
// constexpr int max_n = 200'000 + 5;

int main()
{
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << setprecision(15); // 浮動小数の表示の精度

    int x; cin >> x;
    cout << (x >= 30 ? "Yes" : "No") << "\n";

    return 0;
}


Measured memory_bytes: 3644
#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 dunk(a) cout << (a) << endl
using namespace std;
typedef long long ll;
const int inf = 1001001001;
const int mod = 1000000007;

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

	deque<int> a = { 1 };

	int b = 0;
	rep(i, n - 1) {
		if (a[0] == 2) {
			a.emplace_front(1);
			b = a.size() - 1;
		}
		else {
			a[b]++;
			b--;
		}
	}

	rep(i,a.size()) {
		dunk(a[i]);
	}
	
	return 0;
}

Measured memory_bytes: 256
use proconio::{input, fastout};
use proconio::marker::{Chars};
use proconio::marker::Usize1;
use std::cmp::*;

macro_rules! debug {
      ($($a:expr),*) => {
          eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

#[fastout]
fn main() {
    input!{
        n: Chars,
    }
    let mut digit = 0;
    for i in 0..n.len() {
        let num = n[i].to_digit(10).unwrap();
        digit += num;
    }
    let num1: String = n.iter().collect();
    let num2: u32 = num1.parse().unwrap();
    if num2%digit==0 {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 2200
#include <bits/stdc++.h>
template <typename T>
class BIT {
    int sz;
public:
    std::vector<T> node;
    BIT(int sz): sz(sz+1), node(std::vector<T>(sz+1, 0)) {}
    void add(int idx, T val) {
        ++idx;
        assert(0 < idx && idx < sz);
        while(idx < sz) {
            node[idx] += val;
            idx += idx & -idx;
        }
    }
    T sum(int idx) {
        ++idx;
        assert(0 < idx && idx < sz);
        T res = 0;
        while(idx > 0) {
            res += node[idx];
            idx -= idx & -idx;
        }
        return res;
    }
};
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<int, int>;
const double eps = 1e-8;
const ll MOD = 1000000007;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;
template <typename T1, typename T2>
bool chmax(T1 &a, const T2 &b) {
  if(a < b) {a = b; return true;}
  return false;
}
template <typename T1, typename T2>
bool chmin(T1 &a, const T2 &b) {
  if(a > b) {a = b; return true;}
  return false;
}
template<typename T1, typename T2>
ostream& operator<<(ostream &os, const pair<T1, T2> p) {
  os << p.first << ":" << p.second;
  return os;
}
template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  for(int i=0;i<((int)(v.size()));++i) {
    if(i) os << " ";
    os << v[i];
  }
  return os;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  string s; cin >> s;
  map<char, int> mp;
  int sz = (int)(s.size());
  for(int i=0;i<(sz);++i) {
    mp[s[i]]++;
  }
  int cnt = 0;
  vector<P> p(sz);
  for(int i=0;i<(sz);++i) {
    p[i].first = -1;
    p[i].second = i;
  }
  for(auto &e: mp) {
    if(e.second % 2) {
      cnt++;
    }
  }
  if(cnt > 1) {
    cout << -1 << endl;
    return 0;
  }
  map<char, map<int, bool>> mp2;
  for(int i=0;i<(sz);++i) {
    mp2[s[i]][i] = false;
  }
  map<char, map<int, bool>::reverse_iterator> itr;
  for(auto &e: mp2) {
    itr[e.first] = e.second.rbegin();
  }
  int num = 0;
  for(int i=0;i<(sz);++i) {
    if(mp2[s[i]][i]) continue;
    mp2[s[i]][i] = true;
    if(itr[s[i]]->first == i) {
      p[i].first = sz/2;
      continue;
    }
    p[i].first = num;
    p[itr[s[i]]->first].first = sz - 1 - num;
    itr[s[i]]->second = true;
    itr[s[i]]++;
    num++;
  }
  sort((p).begin(),(p).end());
  BIT<ll> bit(sz);
  ll ans = 0;
  for(int i=0;i<(sz);++i) {
    ans += i - bit.sum(p[i].second);
    bit.add(p[i].second, 1);
  }
  cout << ans << endl;
}


Measured memory_bytes: 12948
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//BEGIN CUT HERE
struct LowestCommonAncestor{
  const int MAX_LOG_V = 50;
  
  int n;
  vector<vector<int> > G,par;
  vector<int> depth;
  LowestCommonAncestor(){}
  LowestCommonAncestor(int sz):
    n(sz),G(sz),par(MAX_LOG_V,vector<int>(n)),depth(sz){}

  void add_edge(int u,int v){
    G[u].push_back(v);
    G[v].push_back(u);
  }
  
  void dfs(int v,int p,int d){
    par[0][v]=p;
    depth[v]=d;
    for(int i=0;i<(int)G[v].size();i++){
      if(G[v][i]!=p) dfs(G[v][i],v,d+1);
    }
  }
  
  void build(int r=0){
    dfs(r,-1,0);
    for(int k=0;k+1<MAX_LOG_V;k++){
      for(int v=0;v<n;v++){
	if(par[k][v]<0) par[k+1][v]=-1;
	else par[k+1][v]=par[k][par[k][v]];
      }
    }
  }
  
  int lca(int u,int v){
    if(depth[u]>depth[v]) swap(u,v);
    for(int k=0;k<MAX_LOG_V;k++){
      if((depth[v]-depth[u])>>k&1){
	v=par[k][v];
      }
    }
    if(u==v) return u;
    for(int k=MAX_LOG_V-1;k>=0;k--){
      if(par[k][u]!=par[k][v]){
	u=par[k][u];
	v=par[k][v];
      }
    }
    return par[0][u];
  }

  int distance(int u,int v){
    return depth[u]+depth[v]-depth[lca(u,v)]*2;
  }
};
//END CUT HERE

signed main(){
  int n;
  cin>>n;
  LowestCommonAncestor lca(n);
  for(int i=0;i<n;i++){
    int k;
    cin>>k;
    for(int j=0;j<k;j++){
      int c;
      cin>>c;
      lca.add_edge(i,c);
    }
  }
  lca.build();
  int q;
  cin>>q;
  while(q--){
    int u,v;
    cin>>u>>v;
    cout<<lca.lca(u,v)<<endl;
  }
  return 0;
}
/*
verified on 2017/11/20
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_C&lang=jp
*/

Measured memory_bytes: 31100
#include<bits/stdc++.h>
typedef long long ll;
#define INF 0x3f3f3f3f
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
using namespace std;
const int sz=1001, mod=1e9+7;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,d,i;
    cin>>n>>d;
    cout<<ceil(1.0*n/(2*d+1));
}


Measured memory_bytes: 256