akhauriyash/Code-Regression huggingface dataset:
fun main(args: Array<String>) {
    val pw = java.io.PrintWriter(System.out)
    Problem.solve(java.util.Scanner(System.`in`), pw)
    pw.flush()
}

object Problem {
    fun solve(sc: java.util.Scanner, pw: java.io.PrintWriter) {
        val W = sc.next().toLong()
        val H = sc.next().toLong()
        val x = sc.next().toLong()
        val y = sc.next().toLong()

        val S = (H * W).toDouble() / 2
        val m = if (x * 2 == W && y * 2 == H) 1 else 0
        pw.println("%f %d".format(S, m))
    }
}


Measured memory_bytes: 31136
#include<stdio.h>
int MIN(int a,int b){return a<b?a:b;}
int main(){
  int i,j,n,m,a,b,M=100000,d[100010]={};
  for(i=1;i<M;i++)d[i]=1e9;
  scanf("%d %d",&n,&m);
  for(j=0;j<m;j++){
    scanf("%d %d",&a,&b);
    for(i=0;i<n;i++)d[i+a]=MIN(d[i+a],d[i]+b);
    for(i=M-2;i;i--)d[i]=MIN(d[i],d[i+1]);
  }
  // for(i=0;i<=n;i++)printf("%d ",d[i]);printf("\n");
  printf("%d\n",d[n]);
  return 0;
}


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

int main(){
	string s;
	cin>>s;
	sort(s.begin(), s.end());
	if(s[0]==s[1] && s[2]==s[3] && s[1]!=s[2]){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}
}

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

using ll = long long int;

const int MAX = (int)(1e5 + 5);
const ll INF = (ll)(1e10 + 5);

const int MAX_H = (int)(8e1 + 5);
const int MAX_W = (int)(8e1 + 5);
const int MAX_DIFF = (int)(8e1 + 5);
const int BASE = (MAX_H + MAX_W) * MAX_DIFF;
const int SIZE = 2 * BASE;

int h, w;
int a[MAX_H][MAX_W];
int b[MAX_H][MAX_W];

bitset<SIZE> dp[MAX_H][MAX_W];

int main(void) {
  // Here your code !
  scanf("%d %d", &h, &w);

  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j) {
      scanf("%d", &(a[i][j]));
    }
  }

  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j) {
      scanf("%d", &(b[i][j]));
    }
  }

  int init = abs(a[0][0] - b[0][0]);

  dp[0][0].set(BASE + init);
  dp[0][0].set(BASE - init);

  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j) {
      int diff = abs(a[i][j] - b[i][j]);

      if (i - 1 >= 0) {
        dp[i][j] |= (dp[i - 1][j] << diff);
        dp[i][j] |= (dp[i - 1][j] >> diff);
      }

      if (j - 1 >= 0) {
        dp[i][j] |= (dp[i][j - 1] << diff);
        dp[i][j] |= (dp[i][j - 1] >> diff);
      }
    }
  }

  int ans = SIZE;

  for (int i = 0; i < SIZE; ++i) {
    if (dp[h - 1][w - 1].test(i)) {
      ans = min(ans, abs(i - BASE));
    }
  }

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

  return 0;
}


Measured memory_bytes: 24832
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>

using namespace std;
long long n,ans;
int l,r;
int main()
{
 scanf("%I64d",&n);
 for(int i=1;i<=n;i++)
 {
 	cin>>l>>r;
  ans+=(r-l+1);
 }
	cout<<ans<<endl;
 return 0;
}


Measured memory_bytes: 256
N,M=map(int,input().split())

yp_dic={}
yplist=[]
for i in range(M):
  p,y=map(int,input().split())
  if p not in yp_dic:
    yp_dic[p]=[]
  yp_dic[p].append(y)
  yplist.append((y,p))

for key in yp_dic:
  yp_dic[key].sort()

#print(yp_dic)
all_dic={}
for pref,ylist in yp_dic.items():
  pref_dic={}
  for i,y in enumerate(ylist):
    pref_dic[y]=i+1
  all_dic[pref]=pref_dic

#print(all_dic)
for y,p in yplist:
  id="{:0>6}{:0>6}".format(p,all_dic[p][y])
  print(id)
  #print(y,p,all_dic[p][y])


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

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

  int A;
  set<int> st;
  rep(i, N) {
    cin >> A;
    st.insert(A);
  }

  if (N == st.size())
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
  return 0;
}

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

int const N = 200;
vector<int> g[N + 1];
int d[N + 1], n, cl[N + 1];
bool vis[N + 1];
char s[N + 2];
queue<int> q;

int bfs(int v){
	f(i, 1, n + 1)vis[i] = false;
	d[v] = 0;
	vis[v] = true;
	q.push(v);
	int an = 0;
	while (!q.empty()){
		v = q.front();
		q.pop();
		for (int u: g[v])if (!vis[u]){
			vis[u] = true;
			d[u] = d[v] + 1;
			if (d[u] > an)an = d[u];
			q.push(u);
		}
	}
	return an;
}

bool bi(int v = 1, int c = 1){
	if (cl[v])return cl[v] == c;
	cl[v] = c;
	for (int u: g[v])if (!bi(u, c ^ 3))return false;
	return true;
}

int main(){
	scanf("%d", &n);
	f(i, 1, n + 1){
		scanf("%s", s + 1);
		f(j, 1, n + 1)if (s[j] == '1')g[i].push_back(j);
	}
	if (!bi()) { printf("-1\n"); return 0; }
	int an = 0;
	f(i, 1, n + 1)an = max(an, bfs(i));
	printf("%d\n", an + 1);
}

Measured memory_bytes: 512
#include <iostream>
#include <stdio.h>

#include <bits/stdc++.h>
using namespace std;

int main()
{
  int s=0,i,j;
  string x;
  cin>>x;
  for(i=0,j=x.size()-1;j>0;i++,j--)
  {
      if(x[i]!=x[j])
        {s++;
        x[i]=x[j];}
  }
  cout<<s;

     return 0;
}


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

int main(){
    int N;
    cin >> N;
    int n_tmp = N;
    int sum_digits = 0;

    while(n_tmp > 0){
        sum_digits += n_tmp % 10;
        n_tmp /= 10;
    }

    bool flg = N % sum_digits == 0;

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

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
using namespace std;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll inf = 1LL << 60;
#define all(x) (x).begin(),(x).end()
#define puts(x) cout << x << endl
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)

vector<vector<int>>e;
vector<int>e2[5050];
ll d[5050];
int used[5050];
int N, M, P;

int dfs(int now,int to) {
	used[now] = 1;
	if (now == to)return 1;
	fore(x, e2[now]) {
		if (!used[x]) {
			if (dfs(x, to))return 1;
		}
	}
	return 0;
}

int check(int v) {
	int c1 = dfs(0, v);
	memset(used, 0, sizeof(used));
	int c2 = dfs(v, N - 1);
	return c1 && c2;
}
bool shortest_path(int s, int t) {
	for (int i = 0; i < N;i++)d[i] = inf;
	d[s] = 0;
	for (int i = 0; i <= N; i++)for (int j = 0; j < M; j++) {
		auto edge = e[j];
		int from = edge[0];
		int to = edge[1];
		int cost = edge[2];
		if (d[from] != inf && d[to] > d[from] + cost) {
			d[to] = d[from] + cost;
			if (i == N && check(to))return true;
		}
	}
	return false;
}

int main() {
	cin >> N >> M >> P;
	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		a--, b--;
		e.pb({a,b,-c+P});
		e2[a].pb(b);
	}
	int c = shortest_path(0,N-1);
	if (c)puts(-1);
	else puts(max(0LL,-d[N-1]));


	return 0;
}

Measured memory_bytes: 896
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;


int main() {
    int N, M;
    cin >> N >> M;
    vector<int> a(N), b(N);
    vector<int> c(M), d(M);
    for(int i=0; i<N; ++i) {
        cin >> a[i] >> b[i];
    }
    for(int i=0; i<M; ++i) {
        cin >> c[i] >> d[i];
    }
    for(int i=0; i<N; ++i) {
        int res = 0;
        for(int j=0; j<M; ++j) {
            if(abs(a[i]-c[res]) + abs(b[i]-d[res]) > abs(a[i]-c[j]) + abs(b[i]-d[j])) {
                res = j;
            }
        }
        cout << res+1 << endl;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
# define mod 100000
int main()
{
    ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n,m;
	cin>>n>>m;
	if(n==m)
	cout<<"Yes"<<endl;
	else
	cout<<"No"<<endl;
}



Measured memory_bytes: 256
from bisect import bisect_left, bisect_right
n = int(input())
ls = sorted(list(map(int, input().split())))
total = 0
for i in range(n):
    for j in range(i+1, n):
        b, c = ls[i], ls[j]
        lower = abs(b-c) + 0.5
        upper = b+c - 0.5
        ii = bisect_left(ls, lower)
        jj = bisect_left(ls, upper)
        cnt = jj - ii
        if ii <= i < jj:
            cnt -= 1
        if ii <= j < jj:
            cnt -= 1
        total += cnt
total //= 3

print(total)


Measured memory_bytes: 49368
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1000000000LL;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int func(int n){
  int res = 0;
  for(int i = 0; n > 0; i++){
  int mod = n % 10;
  res += mod;
  n /= 10;
  }
  return res;
}

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

  if(n % func(n) == 0) cout << "Yes" << ln;
  else cout << "No" << ln;
}
  


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

int main()
{
    int N, M, X;
    cin >> N >> M >> X;
    int A[M];
    for(int i = 0; i < M; ++i) cin >> A[i];

    int k;
    for(k = 0; A[k] < X; ++k);
    cout << min(M-k, k) << endl;
    
    return 0;
}

Measured memory_bytes: 256
import sys

aa = input().strip().split()
h = int(aa[0])
w = int(aa[1])
a = [list(input().strip()) for _ in range(h)]
r = [list() for _ in range(2)]

for i in range(h):
    if a[i][0] == '.':
        flag = True

        for j in range(1, w):
            if a[i][j] != '.':
                flag = False
                break

        if flag:
            r[0].append(i)

for i in range(w):
    if a[0][i] == '.':
        flag = True

        for j in range(1, h):
            if a[j][i] != '.':
                flag = False
                break

        if flag:
            r[1].append(i)

for i in reversed(range(len(r[0]))):
    del a[r[0][i]]

for i in reversed(range(len(r[1]))):
    for j in reversed(range(len(a))):
        del a[j][r[1][i]]

for i in range(len(a)):
    for j in range(len(a[i])):
        sys.stdout.write(a[i][j])

    sys.stdout.write('\n')


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

int main() {
    string s; cin >> s;
    s = '0'+ s;
    int n = s.size();

    int cnt = 0;
    for(int i = n-1; i >= 0; i--){
        int si = s[i]-'0';
        if(si >= 10){
            si -= 10;
            s[i-1]++;
        }

        if(si < 5){
            cnt += si;
            //cout << "a" << endl;
        }
        else if(si > 5){
            cnt += 10-si;
            if(i == 0) cnt++;
            else s[i-1]++;
            //cout << "b" << endl;
        }
        else{
            int sk;
            for(int j = i-1; j >= 0; j--){
                if(s[j] != 5){
                    sk = s[j];
                    break;
                }
            }
            if(sk < '5'){
                cnt += si;
                //cout << "c" << endl;
            }
            else{
                cnt += 10-si;
                if(i == 0) cnt++;
                else s[i-1]++;
                //cout << "d" << endl;
            }
        }
    }
    cout << cnt << endl;
}


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

int main(){
    // Your code here!
    int a,b,c;



    while(true){
        cin>>a>>b;
        if(a==0&&b==0){
            break;
        }
        c=0;
        for(int v=1;v<=a;v++){
            for(int l=v+1;l<=a;l++){
                for(int y=l+1;y<=a;y++){
                    if(v+l+y==b)c+=1;
                }
            }
        }        
        cout<<c<<endl;
    }



}



Measured memory_bytes: 3088
package main

import "fmt"

func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func main() {
	var a, b int

	fmt.Scan(&a)
	fmt.Scan(&b)

	var r int
	r = max(a+b, a-b)
	r = max(r, a*b)

	fmt.Println(r)
}


Measured memory_bytes: 1772
str = input()
num = [int(str[0]), int(str[2]), int(str[4])]

if num[0] == num[1] and num[0] != num[2]:
    print("Yes")
elif num[0] != num[1] and num[1] == num[2]:
    print("Yes")
elif num[0] == num[2] and num[0] != num[1]:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001001001001
#define mod 1000000007
#define mod2 998244353
#define pi acos(-1)
#define all(v) v.begin(),v.end()
int main(){
    int n,m;cin>>n>>m;
    n--;m--;
    cout<<n*m<<endl;
}


Measured memory_bytes: 3560
//package com.beginner.b051;
import java.util.Scanner;

public class Main {

    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        int K = sc.nextInt();
        int S = sc.nextInt();
        int sum = 0;
        for(int i=0;i<=K;i++){
            for(int j=0;j<=K;j++){
                if(S-i-j>=0&&S-i-j<=K){
                    //System.out.println(i+" "+j+" " + (S-i-j));
                    sum++;
                }
            }

        }
//        if(S%3==0&&S/3<=K){
//            sum-=2;
//        }
        System.out.println( sum);
        sc.close();
    }

}

Measured memory_bytes: 9684
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <set>
#include <map>
#include <cassert>
#include <numeric>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
	#define eprintf(...) 42
#endif

typedef long long int int64;


const int N = (int) 4e5 + 100;
vector <pair <int, int> > g[N];
int par[N];
int sz[N];

int getP(int x)
{
	if (par[x] == x) return x;
	return par[x] = getP(par[x] );
}

bool add(int a, int b)
{
	a = getP(a);
	b = getP(b);
	if (a == b) return false;
	if (sz[a] > sz[b] )
	{
		sz[a] += sz[b];
		par[b] = a;
	}
	else
	{
		sz[b] += sz[a];
		par[a] = b;
	}
	return true;
}
int a[N], b[N], c[N];

int main(int,  char **)
{
#ifdef LOCAL
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

	int n, q;
	scanf("%d%d", &n, &q);
	
	for (int i = 0; i < n; i++)
	{
		sz[i] = 1;
		par[i] = i;
	}

	int minC = (int) 1e9 + 100;
	for (int i = 0; i < q; i++)
	{
		scanf("%d%d%d", &a[i], &b[i], &c[i]);
		minC = min(minC, c[i] );
	}

	long long ans = (n - 1) * 1LL * minC;
	for (int i = 0; i < q; i++)
	{
		if (c[i] - minC > n) continue;
		g[c[i] - minC].emplace_back(a[i], b[i]);
		g[c[i] - minC + 1].emplace_back( (a[i] + 1) % n, b[i]);
	}
	
	for (int i = 0; i < N; i++)
	{
		for (auto p : g[i] )
		{
//			eprintf(">>> %d %d\n", p.first, p.second);
			if (add(p.first, p.second) )
			{
//				eprintf("%d : %d %d\n", i, p.first, p.second);
				ans += i;
				g[i + 2].emplace_back((p.first + 1) % n, (p.second + 1) % n);
			}
		}
	}

	printf("%lld\n", ans);

	return 0;
}



Measured memory_bytes: 22912
import sys

while True:
    n, m = map(int, sys.stdin.readline().split())
    if n == 0 and m ==0:
        break
    
    taro = []
    for i in xrange(n):
        x = int(sys.stdin.readline())
        
        taro.append(x)
    hanako = []
    for i in xrange(m):
        x = int(sys.stdin.readline())
        
        hanako.append(x)
    
    sum_taro = sum(taro)
    sum_hanako = sum(hanako)
    
    diff = -(sum_taro - sum_hanako) / 2.0
    if diff != int(diff):
        print -1
        continue
    MAX = max(taro + hanako) + 1
    result = MAX
    for t in taro:
        if t + diff in hanako:
            if result > t:
                result = t
    if result != MAX:
        print result, int(result + diff)
    else:
        print -1

Measured memory_bytes: 4280
s=list(input())
m=len(s)
a=[0]*(m+1)
add=1
for i in range(m):
    if s[i]=="<":
        a[i+1]+=add
        add+=1
    else:
        add=1
for i in range(m-1,-1,-1):
    if s[i]==">" and a[i]<=a[i+1]:
        a[i]+=a[i+1]-a[i]+1
print(sum(a))

Measured memory_bytes: 32472
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>
int n, t;
std::vector<int> a, f;
std::vector<std::vector<std::vector<long long>>> dp;
void dfs(int d, int s, int l, int r) {
    if (d == n - 1)
        return;
    f[s << 1] = l;
    f[s << 1 | 1] = r;
    dfs(d + 1, s << 1, l, l + r);
    dfs(d + 1, s << 1 | 1, l + r, r);
}
long long solve(int l, int r, int x) {
    if (r - l == 1)
        return 0;
    if (dp[l][r][x] != -1)
        return dp[l][r][x];
    long long ans = 1'000'000'000'000'000'000;
    for (int m = l + 1; m < r; ++m)
        ans = std::min(ans, solve(l, m, x << 1) + solve(m, r, x << 1 | 1) + 1LL * a[m] * (f[x << 1] + f[x << 1 | 1]));
    return dp[l][r][x] = ans;
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> n;
    a.resize(n);
    f.resize(1 << (n - 1));
    dp.assign(n, std::vector<std::vector<long long>>(n));
    for (int l = 0; l < n; ++l)
        for (int r = l + 2; r < n; ++r)
            dp[l][r].assign(1 << (n - r + l), -1);
    for (int i = 0; i < n; ++i)
        std::cin >> a[i];
    dfs(1, 1, 1, 1);
    std::cout << a[0] + a[n - 1] + solve(0, n - 1, 1) << "\n";
    return 0;
}

Measured memory_bytes: 16256
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <cmath>
#include <string>
#include <iterator>
#include <vector>
 
using namespace std;

typedef long long ll;
typedef long double ld;
#define L(ID) ((ID*2)+1)
#define R(ID) ((ID*2)+2)
#define M(L,R) ((L+R)/2)
#define forr(start,end) for(int i = start; i < end; i++)
#define gap ' '
 
const int MAXN = 1e6 + 5;


int largest(int a, int b){
	return (a<b)?b:a;
}


int main() {
	int grid[3][3];
	for(int i = 0; i < 3; ++i){
		for(int j = 0; j < 3; ++j){
			cin >> grid[i][j];
		}
	}
	int n = 0;
	cin >> n;
	vector<int> a(n);
	for(int i = 0; i < n; ++i){
		cin >> a[i];
	}
	for(int k = 0; k < n; ++k){
		for(int i = 0; i < 3; ++i){
			for(int j = 0; j < 3; ++j){
				if(a[k] == grid[i][j]){
					grid[i][j] = -1;
				}
			}
		}
	}
	for(int i = 0; i < 3; ++i){
		int cnt = 0;
		for(int j = 0; j < 3; ++j){
			if(grid[i][j] == -1){
				++cnt;
			}
		}
		if(cnt == 3){
			cout << "Yes" << endl;
			return 0;
		}
	}
	if(grid[0][0] == -1 and grid[1][1] == -1 and grid[2][2] == -1){
		cout << "Yes" << endl;
		return 0;
	}
	if(grid[0][2] == -1 and grid[1][1] == -1 and grid[2][0] == -1){
		cout << "Yes" << endl;
		return 0;
	}
	for(int j = 0; j < 3; ++j){
		int cnt = 0;
		for(int i = 0; i < 3; ++i){
			if(grid[i][j] == -1){
				++cnt;
			}
		}
		if(cnt == 3){
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;


    return 0;
} 

Measured memory_bytes: 888
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <random>
#include <tuple>
#include <iomanip>
#include <cstring>

using namespace std;

typedef long long ll;
//typedef pair<int,int> Pint;
//typedef pair<ll, ll> P;
//typedef pair<ll, pair<ll, ll>> P;
//typedef tuple<int,int,int> T;
typedef vector<ll> vec;
typedef vector<vec> mat;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define revrep(i, n) for(ll i = (n-1); i >= 0; i--)
#define pb push_back
#define f first
#define s second
//const ll INFL = 1LL << 60;//10^18 = 2^60
const ll INFL = 1LL << 60;
const int INF = 1 << 30;//10^9
ll MOD = 1e9 + 7;
//ll MOD  = 998244353;
vector<ll> dy = {0, 0, 1, -1, 1, 1, -1, -1, 0};
vector<ll> dx = {1, -1, 0, 0, 1, -1, 1, -1, 0};

ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll pow_long(ll x, ll k){
  ll res = 1;
  while(k > 0){
    if(k % 2) res *= x;
    x *= x;
    k /= 2;
  }
  return res;
}
ll pow_mod(ll x, ll k){
  x %= MOD; x += MOD; x %= MOD;
  ll res = 1;
  while(k > 0){
    if(k % 2){
      res *= x; res %= MOD;
    }
    x *= x; x %= MOD;
    k /= 2;
  }
  return res;
}
ll inverse(ll x){return pow_mod(x, MOD - 2);};

//最大公約数
ll gcd(ll a, ll b){
    if(b == 0) return a;
    return gcd(b, a % b);
}

//最小公倍数
ll lcm(ll x, ll y){return x / gcd(x, y) * y;};

//コンビネーション
const int MAXcomb = 200010;
ll fac[MAXcomb], finv[MAXcomb], inv[MAXcomb];
//facはn!,finvは1/n!
//invは逆元
void COMinit(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < MAXcomb; i++){
        fac[i] = fac[i-1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
        finv[i] = finv[i-1] * inv[i] % MOD;
    }
}
ll comb(int n, int k){
    if(n < k) return 0;
    if(n < 0 || k < 0) return 0;
    return fac[n] * finv[k] % MOD * finv[n-k] % MOD;
}

ll kai_mod(ll x){
  if(x == 1) return 1;
  return x * kai_mod(x-1) % MOD;
}


ll N, Q;

vector<ll> E[200010];
vector<ll> ans(200010);
vector<ll> query(200010);

void dfs(ll now, ll from){
  ans[now] += query[now];
  for(ll to : E[now]){
    if(to == from) continue;
    query[to] += query[now];
    dfs(to, now);
  }
}

int main(void){
  string S, T;
  cin >> S >> T;
  vector<ll> X[30];
  rep(i, S.size()){
    X[S[i] - 'a'].pb(i);
  }

  rep(i, T.size()){
    if(X[T[i] - 'a'].size() == 0){
      cout << -1 << endl;
      return 0;
    }
  }

  rep(i, S.size()){
    X[S[i] - 'a'].pb(i + S.size());
  }
  ll now = -1;
  ll ans = 0;
  rep(i, T.size()){
    ll x = *upper_bound(X[T[i] - 'a'].begin(), X[T[i] - 'a'].end(), now);
    ans += x - now;
    now = x;
    now %= S.size();
  }
  cout << ans << endl;







}


Measured memory_bytes: 12088
#include <stdio.h>

int main(void){
  int input,lowest;
  scanf("%d",&input);
  lowest = input % 10;
  switch (lowest){
    case 2:
    case 4:
    case 5:
    case 7:
    case 9:
      printf("hon\n");
      break;
    case 0:
    case 1:
    case 6:
    case 8:
      printf("pon\n");
      break;
    case 3:
      printf("bon\n");
      break;
    default:
      printf("error\n");
      break;
  }
  return 0;
}

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

namespace ABC045A
{
    class Program
    {
        static void Main(string[] args)
        {
            int a, b, h,x;
            a = int.Parse(Console.ReadLine());
            b = int.Parse(Console.ReadLine());
            h = int.Parse(Console.ReadLine());
            x = (a + b)*h / 2 ;
            Console.WriteLine(x);
            Console.ReadKey();
        }
    }
}

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

int main(){
    int t, t1, x1, y1, t2 = 0, x2 = 0, y2 = 0, n, i;
    cin >> n;
    for(i=0; i<n; i++){
        cin >> t1 >> x1 >> y1;
        t = t1 - t2 - abs(x1-x2) - abs(y1-y2);
        if(t<0 || t%2 == 1){
            cout << "No";
          	break;
        }
        if(i == n-1){
            cout << "Yes";
        }
        t2 = t1;
        x2 = x1;
        y2 = y1;
    }
    return 0;
}

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

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

  int s, w;
  cin >> s >> w;

  if (w >= s) cout << "unsafe\n";
  else cout << "safe\n";

  return (0);
}

Measured memory_bytes: 3636
#include <iostream>
#include<bits/stdc++.h>
#define ll long long
#define ld double
using namespace std;
char x[200000],y[200000];
const ll mod=1e9+7;
ll b[500000];

int main()
{
    ll i,n,m,j,k=0,l=0;
    scanf("%lld",&n);
    scanf("%s %s",x,y);
    for(i=0;i<n;i++)
    {
        if((i+1<n)&&x[i]==x[i+1])
        {
            b[++k]=2;
            i++;
        }else
        {
            b[++k]=1;
        }
    }
    if(b[1]==1)
    {
        l=3;
    }else
    {
        l=6;
    }
    for(i=1;i<k;i++)
    {
        if(b[i]==1&b[i+1]==2)
        {
            l=(l*2)%mod;
        }if(b[i]==1&&b[i+1]==1)
        {
            l=(l*2)%mod;
        }if(b[i]==2&&b[i+1]==1)
        {
            l=l;
        }if(b[i]==2&&b[i+1]==2)
        {
            l=(l*3)%mod;
        }
    }
    printf("%lld\n",l);
    return 0;
}


Measured memory_bytes: 2304
import sys
import random

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

D = int(input())
c = list(map(int,input().split()))
s = [list(map(int,input().split())) for i in range(D)]
#t = [int(input()) for i in range(D)]
#M = int(input())
#Q = [list(map(int,input().split())) for i in range(M)]

def content(t):
    cont = 0
    last = [0]*26
    for i in range(D):
        cont += s[i][t[i]-1]
        last[t[i]-1] = i+1
        for j in range(26):
            cont -= c[j]*(i+1-last[j])
    return cont

def main():
    t = [random.randint(1,26) for i in range(D)]
    prev = content(t)
    for i in range(100):
        d,q = random.randint(0,D-1), random.randint(1,26)
        prev_t = t[d]
        t[d] = q
        now = content(t)
        if prev>content(t):
            t[d] = prev_t
        else:
            prev=now
    for a in t:
        print(a)


if __name__ == '__main__':
    main()





Measured memory_bytes: 83896
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;


public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		ArrayList<Integer> list = new ArrayList<Integer>();
		String[] str = sc.nextLine().split("[\\s]");
		int i = 0;
		
		for(String r:str){
			int tmp = Integer.parseInt(r);
			list.add(tmp);
			if(i == 4)
				break;
			i++;
		}
		
		Collections.sort(list);
		Collections.reverse(list);
		
		for(int j = 0;;j++){
			System.out.print(list.get(j));
			if(j == 4)
				break;
			System.out.print(" ");
		}
		System.out.println();
	}
}

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

using namespace std;


int main() {
    int N, M;
    int si, ci;
    bool ans = false;
    cin >> N >> M;
    vector<pair<int, int>> p(M);
    rep(i, M) cin >> p[i].first >> p[i].second;
    rep(x, 1000) {
        int keta = 1;
        int nx = x / 10;
        vector<int> d(1, x % 10);
        while (nx > 0) {
            keta++;
            d.push_back(nx % 10);
            nx /= 10;
        }
        if (keta != N)continue;
        bool ok = true;
        reverse(d.begin(), d.end());
        rep(i, M) {
            if (d[p[i].first - 1] != p[i].second) ok = false;
        }
        if (ok) {
            cout << x << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}


Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define lfs cout<<fixed<<setprecision(10)
#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define fi first
#define se second
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define EB emplace_back
#define rep(i,n,m) for(ll i = (n); i < (ll)(m); i++)
#define rrep(i,n,m) for(ll i = (ll)(m) - 1; i >= (ll)(n); i--)
using ll = long long;
using ld = long double;
const ll MOD1 = 1e9+7;
const ll MOD9 = 998244353;
const ll INF = 1e18;
using P = pair<ll, ll>;
template<typename T1, typename T2>
bool chmin(T1 &a,T2 b){if(a>b){a=b;return true;}else return false;}
template<typename T1, typename T2>
bool chmax(T1 &a,T2 b){if(a<b){a=b;return true;}else return false;}
ll median(ll a,ll b, ll c){return a+b+c-max({a,b,c})-min({a,b,c});}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
template<typename T1,typename T2>
void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;}  
template<typename T>
void debug(vector<vector<T>>&v,ll h,ll w){for(ll i=0;i<h;i++)
{cout<<v[i][0];for(ll j=1;j<w;j++)cout spa v[i][j];cout<<endl;}};
void debug(vector<string>&v,ll h,ll w){for(ll i=0;i<h;i++)
{for(ll j=0;j<w;j++)cout<<v[i][j];cout<<endl;}};
template<typename T>
void debug(vector<T>&v,ll n){if(n!=0)cout<<v[0];
for(ll i=1;i<n;i++)cout spa v[i];cout<<endl;};
template<typename T>
vector<vector<T>>vec(ll x, ll y, T w){
  vector<vector<T>>v(x,vector<T>(y,w));return v;}
ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;}
vector<ll>dx={1,-1,0,0,1,1,-1,-1};
vector<ll>dy={0,0,1,-1,1,-1,1,-1};
template<typename T>
vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
template<typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v(ts...))>(a,make_v(ts...));
}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2>&p){
  return os << p.first << " " << p.second;
}
//mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());

int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  ll res=0,buf=0;
  bool judge = true;
  ll x,n;cin>>x>>n;
  vector<ll>p(n);
  rep(i,0,n)cin>>p[i];
  vector<bool>sz(200);
  rep(i,0,n)sz[p[i]]=true;
  rep(i,0,200){
    if(!sz[x-i]){
      cout<<x-i<<endl;
      return 0;
    }
    if(!sz[x+i]){
      cout<<x+i<<endl;
      return 0;
    }
  }
  return 0;
}

Measured memory_bytes: 3644
from itertools import accumulate
n = int(input())
s = input()

r_acc = [0] + list(accumulate([int(s[i] == 'R') for i in range(n)]))
g_acc = [0] + list(accumulate([int(s[i] == 'G') for i in range(n)]))
b_acc = [0] + list(accumulate([int(s[i] == 'B') for i in range(n)]))

ans = 0
for i in range(n):
    for j in range(i + 1, n):
        si = s[i]
        sj = s[j]
        if si == sj:
            continue
        if (si == 'R' and sj == 'G') or (si == 'G' and sj == 'R'):
            ans += b_acc[n] - b_acc[j]
            if n >= j + j - i + 1:
                ans -= b_acc[j + j - i + 1] - b_acc[j + j - i]
        elif (si == 'R' and sj == 'B') or (si == 'B' and sj == 'R'):
            ans += g_acc[n] - g_acc[j]
            if n >= j + j - i + 1:
                ans -= g_acc[j + j - i + 1] - g_acc[j + j - i]
        else:
            ans += r_acc[n] - r_acc[j]
            if n >= j + j - i + 1:
                ans -= r_acc[j + j - i + 1] - r_acc[j + j - i]
print(ans)


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

int main()
{
	long long n,ans=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		if(!(i%3==0 || i%5==0)){
			ans+=i;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define rep(i,m,n) for(int i=m;i<n;i++)
#define c(n) cin>>n
#define co(n) cout<<n<<endl
using namespace std;

int main(){
  int a,b,c=0,d=0,e,n,m,x,y;
  c(n);
  int xx[n];
  rep(i,0,n){
    c(xx[i]);
    c+=xx[i];
    d=max(d,xx[i]);
  }
  co(c-d/2);
  
  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main{
	
	public static void main(String[] args){
		
		Scanner s = new Scanner(System.in);
		
			int n = s.nextInt();
			int d = s.nextInt();
			
			long[] x = new long[n];
			long[] y = new long[n];
			
			int counter = 0;
			
			for(int i = 0; i < n; i++){
				
				x[i] = s.nextInt();
				y[i] = s.nextInt();
				
			}
			
			for(int i = 0; i < n; i++){
				
				double temp = Math.sqrt(x[i] * x[i] + y[i] * y[i]);
				
				if(temp <= d){
					counter++;
				}
				
			}
			
			System.out.println(counter);
			
		}
	
}


Measured memory_bytes: 62768
#pragma GCC optimize("O3", "unroll-loops")
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <bitset>
#include <sstream>
#include <deque>
#include <queue>
#include <complex>
#include <random>
#include <cassert>
#include <chrono>

using namespace std;

#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define FIXED cout << fixed << setprecision(12)
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define graph vector<vector<int>>
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define f first
#define s second
#define hashmap unordered_map
#define hashset unordered_set
#define eps 1e-9
#define mod 1000000007
#define inf 3000000000000000007ll
#define sz(a) signed(a.size())
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

#ifdef DEBUG
    mt19937 gen(857204);
#else
    mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

template<class T, class U> inline void checkmin(T &x, U y) { if (y < x) x = y; }
template<class T, class U> inline void checkmax(T &x, U y) { if (y > x) x = y; }
template<class T, class U> inline bool ifmax(T &x, U y) { if (y > x) return x = y, true; return false; }
template<class T, class U> inline bool ifmin(T &x, U y) { if (y < x) return x = y, true; return false; }
template<class T> inline void sort(T &a) { sort(all(a)); }
template<class T> inline void rsort(T &a) { sort(rall(a)); }
template<class T> inline void reverse(T &a) { reverse(all(a)); }
template<class T, class U> inline istream& operator>>(istream& str, pair<T, U> &p) { return str >> p.f >> p.s; }
template<class T> inline istream& operator>>(istream& str, vector<T> &a) { for (auto &i : a) str >> i; return str; }
template<class T> inline T sorted(T a) { sort(a); return a; }

bool check(string &s, int l, int r) {
    while (l < r) {
        if (s[l] != s[r]) return false;
        ++l, --r;
    }
    return true;
}

signed main() {
    FAST; FIXED;
    string s;
    cin >> s;
    int n = sz(s);
    if (check(s, 0, n - 1) && check(s, 0, (n - 1) / 2 - 1) && check(s, (n + 3) / 2 - 1, n - 1)) cout << "Yes";
    else cout << "No";
    #ifdef DEBUG
        cerr << "Runtime is: " << clock() * 1.0 / CLOCKS_PER_SEC << endl;
    #endif
    return 0;
}

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

#define ll long long

ll n, k, cache[int(1e5)];
vector <ll> h;

ll dp(ll ix)
{
	if (ix == n - 1)
		return 0;
	if (ix >= n)	return 2e9;
	if (cache[ix] != -1)	return cache[ix];
	ll ret = 2e9;
	for (ll i = 1; i <= k; i ++){
		ret = min(abs(h[ix] - h[ix + i]) + dp(ix + i), ret);
	}
	return cache[ix] = ret;
}

int main()
{	
	ll _n, _k;	cin >> _n >> _k;	vector <ll> _h(_n);	for (ll i = 0; i < _n; i ++)	cin >> _h[i];
	n = _n;	h = _h;	k = _k;	memset(cache, -1, sizeof(cache));
	cout << dp(0) << "\n";
}

Measured memory_bytes: 8832
import           Control.Applicative
import           Control.DeepSeq
import           Control.Monad
import           Control.Monad.ST
import qualified Data.Array                    as A
import qualified Data.Array.IArray             as IA
import qualified Data.Array.IO                 as AI
import qualified Data.Array.MArray             as MA
import qualified Data.Array.ST                 as STA
import qualified Data.Array.Unboxed            as AU
import           Data.Bits
import qualified Data.ByteString.Char8         as BS
import           Data.Char
import qualified Data.Graph                    as G
import           Data.Int
import qualified Data.IntMap                   as IM
import qualified Data.IntSet                   as IS
import           Data.List
import qualified Data.Map.Strict               as M
import           Data.Maybe
import           Data.Ord
import qualified Data.Sequence                 as SQ
import qualified Data.Set                      as S
import           Data.Time
import qualified Data.Tree                     as T
import qualified Data.Vector                   as V
import qualified Data.Vector.Mutable           as VM
import qualified Data.Vector.Unboxed           as VU
import qualified Data.Vector.Unboxed.Mutable   as VUM

readInt :: IO Int
readInt = fst . fromJust . BS.readInt <$> BS.getLine

readInts :: IO [Int]
readInts = map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine

readIntLists :: Int -> IO [[Int]]
readIntLists n = replicateM n readInts

readInteger :: IO Integer
readInteger = fst . fromJust . BS.readInteger <$> BS.getLine

readIntegers :: IO [Integer]
readIntegers = map (fst . fromJust . BS.readInteger) . BS.words <$> BS.getLine

readIntegerLists :: Int -> IO [[Integer]]
readIntegerLists n = replicateM n readIntegers

readStrings :: IO [String]
readStrings = map BS.unpack . BS.words <$> BS.getLine

readStringLists :: Int -> IO [[String]]
readStringLists n = replicateM n <$> readStrings

toPair :: [a] -> (a, a)
toPair [x, y] = (x, y)

count :: Eq a => a -> [a] -> Int
count a as = length $ filter (== a) as

put :: Show a => a -> IO ()
put = putStr . show

putList :: Show a => [a] -> IO ()
putList [n     ] = put n
putList (n : ns) = do
  put n
  putStr " "
  putList ns

putStrList :: [String] -> IO ()
putStrList [n     ] = putStr n
putStrList (n : ns) = do
  putStr n
  putStr " "
  putStrList ns

yesNoUpper b | b         = putStrLn "YES"
             | otherwise = putStrLn "NO"

yesNo b | b         = putStrLn "Yes"
        | otherwise = putStrLn "No"

divCeiling x n | b == 0    = a
               | otherwise = a + 1
  where (a, b) = x `divMod` n

main = do
  r<-readInt
  print $ 3*r*r

Measured memory_bytes: 380
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdlib>

using namespace std;

#define ALL(c) c.begin(),c.end()
#define RALL(c) c.rbegin(),c.rend()
#define REP(type,i,n) for(type i=0;i<(n);++i)
#define MP(a,b) make_pair((a),(b))
#define F_ first
#define S_ second

typedef long long int lli;
typedef pair<int,int> Pi;

const int INF=100000000;
const long long int INF_=1000000000000000000;

int main(){
	int N;
	cin >> N;
	vector<int> m(394);
	REP(int,i,N){
		int s,l,p;
		cin >> s >> l >> p;
		for(int j=s; j<=l; ++j) m[j]=max(m[j],p);
	}
	REP(int,i,394){
		REP(int,j,i+1){
			m[i]=max(m[i],m[i-j]+m[j]);
		}
	}
	//REP(int,i,9) cout << m[i] << ' ';
	int M;
	cin >> M;
	vector<int> ans;
	bool flag=true;
	REP(int,i,M){
		int w;
		cin >> w;
		if(m[w]==0) flag=false;
		else ans.push_back(m[w]);
	}
	if(!flag) cout << -1 << endl;
	else REP(int,i,ans.size()){
		cout << ans[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 1224
#pragma region
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <vector>
typedef long long ll;
#define rep(i, a, n) for (long long i = a; i <= n; ++i)
#define per(i, a, n) for (long long i = n; i >= a; --i)
#define IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
/*
 *                                                     __----~~~~~~~~~~~------___
 *                                    .  .   ~~//====......          __--~ ~~
 *                    -.            \_|//     |||\\  ~~~~~~::::... /~
 *                 ___-==_       _-~o~  \/    |||  \\            _/~~-
 *         __---~~~.==~||\=_    -_--~/_-~|-   |\\   \\        _/~
 *     _-~~     .=~    |  \\-_    '-~7  /-   /  ||    \      /
 *   .~       .~       |   \\ -_    /  /-   /   ||      \   /
 *  /  ____  /         |     \\ ~-_/  /|- _/   .||       \ /
 *  |~~    ~~|--~~~~--_ \     ~==-/   | \~--===~~        .\
 *           '         ~-|      /|    |-~\~~       __--~~
 *                       |-~~-_/ |    |   ~\_   _-~            /\
 *                            /  \     \__   \/~                \__
 *                        _--~ _/ | .-~~____--~-/                  ~~==.
 *                       ((->/~   '.|||' -_|    ~~-/ ,              . _||
 *                                  -_     ~\      ~~---l__i__i__i--~~_/
 *                                  _-~-__   ~)  \--______________--~~
 *                                //.-~~~-~_--~- |-------~~~~~~~~
 *                                       //.-~~~--\
 *                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 */
#pragma endregion
const int maxn = 105;
const ll mod = 1e9 + 7;
ll a[maxn], b[int(1e5 + 5)], n, k;
ll dp[int(1e5 + 5)];
int main() {
    IO;
    cin >> n >> k;
    rep(i, 1, n) cin >> a[i];
    dp[0] = 1;
    rep(i, 1, n) {
        memset(b, 0, sizeof(b));
        per(j, 0, k) {
            int l = j + 1, r = min(k, j + a[i]);
            if (l <= r) {
                (b[l] += dp[j]) %= mod;
                (b[r + 1] += mod - dp[j]) %= mod;
            }
        }
        ll now = 0;
        rep(i, 0, k) {
            (now += b[i]) %= mod;
            (dp[i] += now) %= mod;
        }
    }
    cout << dp[k] << endl;
}

Measured memory_bytes: 4780
#include "bits/stdc++.h"
#define ll long long
#define lld long double
#define MOD 1000000007
#define inf 1000000000000000000ll
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
ll power(ll x,ll y, ll md=inf){ll res = 1;x%=md;while(y){if(y&1)res = (res*x)%md;x *= x; if(x>=md) x %= md; y >>= 1;}return res;}
 
using namespace std;


#define endl '\n'
#define int ll

signed main() {
	fast;

	int h,w;
	cin>>h>>w;

	pii v[200002];
	for(int i=0;i<h;i++) cin>>v[i].f>>v[i].s;

	map<int,int> mp;
	for(int i=1;i<=w;i++) mp[i] = 0;

	map<int,int> mini = {{0,w}};

	for(int i=0;i<h;i++) {
		int l = v[i].f;
		int r = v[i].s;

		auto it = mp.lower_bound(l);
		int mn = inf;

		while(it!=mp.end() && it->f <= r) {
			mn = min(mn, r+1-(it->f)+(it->s));
			auto it1 = it++;
			mini[it1->s]--;
			if(mini[it1->s]==0) mini.erase(it1->s);
			mp.erase(it1);
		}

		if(r+1<=w && mn<inf) {
			if(it!=mp.end() && it->f == r + 1) {
				if(mp[r+1] > mn) {
					mini[mp[r+1]]--;
					if(mini[mp[r+1]]==0) mini.erase(mp[r+1]);
					mini[mn]++;
					mp[r+1] = mn;
				}
			}
			else {
				mp[r+1] = mn;
				mini[mn]++;
			}
		}

		if(mini.size()) cout<<mini.begin()->f+i+1<<endl;
		else cout<<-1<<endl;

	}
}

Measured memory_bytes: 19248
#include<cstdio>
#include<algorithm>
using namespace std;
struct point {
	int x, y;
	bool operator<(const point &p)const {
		return x != p.x ? x < p.x : y < p.y;
	}
	point operator -(const point &p)const {
		return { x - p.x,y - p.y };
	}
	int Mul(point p) const{
		return x*p.x + y*p.y;
	}
}P[210], OO;

int ccw(point a, point b, point c) {
	return (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);
}

struct Vec {
	point p;
	bool operator<(const Vec &v)const {
		return p.y * v.p.x != v.p.y * p.x ? p.y * v.p.x < v.p.y * p.x : p.Mul(p) < v.p.Mul(v.p);
	}
}w[210];

bool between(point a, point b, point c) {
	return ccw(a, b, c) == 0 && (c - a).Mul(c - b) <= 0;
}

int CC[210], D[210][210], Mod = 998244353, po[210], res, C[210][210];

void Do(int n) {
	int i, j, k;
	if (n <= 1)return;
	for (i = 1; i <= n; i++) {
		CC[i] = 0;
		for (j = 1; j <= n; j++) {
			if (i != j && between(OO, w[i].p, w[j].p))CC[i]++;
		}
	}
	for (i = 1; i <= n; i++)for (j = i + 2; j <= n; j++){
		C[i][j] = 0;
		for (k = i + 1; k < j; k++) if (ccw(w[i].p, w[j].p, w[k].p) >= 0)C[i][j]++;
	}
	for (i = 1; i <= n; i++) {
		for (j = i+1; j <= n; j++) {
			D[i][j] = 0;
			if (between(OO, w[j].p, w[i].p)) continue;
			int c = C[i][j];
			for (k = 1; k < i; k ++) {
				if (ccw(w[k].p, w[i].p, w[j].p) <= 0)continue;
				D[i][j] = (D[i][j] + 1ll * D[k][i] * po[c]) % Mod;
			}
			D[i][j] = (D[i][j] + po[c + CC[i]]) % Mod;
			res = (res + D[i][j]) % Mod;
		}
	}
}

int main() {
	int i, j, n;
	scanf("%d", &n);
	po[0] = 1;
	for (i = 1; i <= n; i++)po[i] = po[i - 1] * 2 % Mod;
	for (i = 0; i < n; i++) {
		scanf("%d%d", &P[i].x, &P[i].y);
	}
	sort(P, P + n);
	for (i = 0; i < n; i++) {
		for (j = i + 1; j < n; j++) {
			w[j - i].p = P[j] - P[i];
		}
		sort(w + 1, w + n - i);
		Do(n - i - 1);
	}
	printf("%d\n", res);
}

Measured memory_bytes: 512
#include <iostream>
#include<cmath>

int sosu_hantei(int X){
    int n,amari;
    n = std::sqrt(X);
    

    if(X <= 3)
        return 1;

    while(1){
        amari = X % n;
        if (!(amari > 0)){
            return 0;
        }
        n = n-1;

        if (n <= 1 )
            break;
    }
    return 1;
}

int main(void){
  
    int X,n,ans;
   
    std::cin >> X;

    while(1){
        if(sosu_hantei(X)){
            std::cout << X;
            return 0;
        }
        X = X +1;
    }
    return 0;
}

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

#define loop(i,n) for(int i = 0;i < int(n);i++)
#define rloop(i,n) for(int i = int(n);i >= 0;i--)
#define range(i,a,b) for(int i = int(a);i <= int(b);i++)
#define SZ(c) int(c.size())
#define ALL(c) c.begin(), c.end()
#define RALL(c) c.rbegin(), c.rend()
#define PI acos(-1)
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define sfi1(v) scanf("%d",&v)
#define sfi2(v1,v2) scanf("%d %d",&v1,&v2)
#define sfi3(v1,v2,v3) scanf("%d %d %d",&v1,&v2,&v3)
#define sfll1(v) scanf("%I64d",&v);
#define sfll2(v1,v2) scanf("%I64d %I64d",&v1,&v2)
#define sfll3(v1,v2,v3) scanf("%I64d %I64d %I64d",&v1,&v2,&v3)
#define endl '\n'

typedef vector<int> vi;
typedef vector<pair<int,int> > vii;
typedef long long ll;
typedef pair<int, int> pii;



int main()
{

#ifndef ONLINE_JUDGE
	//freopen("in.in", "r", stdin);
	//freopen("out.in", "w", stdout);
#endif
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    int k , x;
    cin >> k >> x;
    range(i,x - k + 1 , x + k - 1)cout << i << " ";
    cout << endl;

    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
import java.util.InputMismatchException;
class Main
{
    public static void main(String[] args){
	int n=0;
	long s=0;
	try{
	    Scanner scan = new Scanner(System.in);
	    n = scan.nextInt();
	    s = 0;
	    for (int i=0; i<n; i++){
		s += scan.nextInt();
	    }
	}catch (InputMismatchException e){
	    System.out.println(e);
	}
	System.out.printf("%d\n", s/n);
    }
}

Measured memory_bytes: 42648
#include <iostream>
#include <vector>
using ll = long long;

ll n, q, q_num, c, r, sum, l;
std::vector<int> vec;


int main() {
    r = 0;
    sum = 0;
    std::cin >> n >> q;
    vec.assign(n, 0);
    for (int i = 0; i < n; i++) {
        std::cin >> vec[i];
    }
    for (int i = 0; i < q; i++) {
        std::cin >> q_num;
        sum = 0;
        c = 0;
        r = 0;
        for (l = 0; l < n; l++) {
            while (r < n && sum + vec[r] <= q_num) {
                sum += vec[r];
                r++;
            }
            ll p = r - l;
            c += p;
            sum -= vec[l];
        }
        std::cout << c << std::endl;
    }
}



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

using namespace std;

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

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

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

    ll N,X;cin>>N>>X;
    ll pos;cin>>pos;
    ll res=abs(X-pos);
    for(int i=1;i<N;i++){
      cin>>pos;
      res=gcd(res,abs(X-pos));
    }
    cout<<res<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
#define ll long long

vector<vector<ll>> E;
vector<ll> X;

void dfs(ll i, ll par){
  X[i] += X[par];
  for(int j=0; j<E[i].size(); ++j){
    if(E[i][j] == par) continue;
    dfs(E[i][j], i);
  }
}

int main(){
  ll N, Q;
  cin >> N >> Q;

  for(int i=0; i<=N; ++i){
    E.emplace_back();
    X.emplace_back(0);
  }

  for(int i=0; i<N-1; ++i){
    ll a, b;
    cin >> a >> b;
    E[a].emplace_back(b);
    E[b].emplace_back(a);
  }

  for(int i=0; i<Q; ++i){
    ll p, x;
    cin >> p >> x;
    X[p] += x;
  }

  dfs(1,0);
  for(int i=1; i<=N; ++i) cout << X[i] << " ";
  cout << endl;

  return 0;
}

Measured memory_bytes: 25516
import itertools
ans = 0
nums = []
N = int(input())
for k in range(1, 10):
    s = itertools.product(['3', '5', '7'], repeat = k)
    for seq in s:
        num = ''.join(seq)
        nums.append(num)
for num in nums:
    if '3' in num and '5' in num and '7' in num and int(num) <= N:
        ans += 1
print(ans)

Measured memory_bytes: 5272