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

public class Main {
  private static int calculateDigitsSum(int i) {
    int sum = 0;
    while (i > 0) {
      sum += i % 10;
      i /= 10;
    }
    return sum;
  }
  
  private static int solve(int n, int a, int b) {
    int sum = 0;
    for (int i = 1; i <= n; i++) {
      int digitsSum = calculateDigitsSum(i);
      if (a <= digitsSum && digitsSum <= b) {
        sum += i;
      }
    }
    return sum;
  }
  
  private static void execute(ContestReader reader, PrintWriter out) {
    int n = reader.nextInt();
    int a = reader.nextInt();
    int b = reader.nextInt();
    out.println(solve(n, a, b));
  }
  
  public static void main(String[] args) {
    ContestReader reader = new ContestReader(System.in);
    PrintWriter out = new PrintWriter(System.out);
    execute(reader, out);
    out.flush();
  }
}

class ContestReader {
  private BufferedReader reader;
  private StringTokenizer tokenizer;
  
  ContestReader(InputStream in) {
    reader = new BufferedReader(new InputStreamReader(in));
  }
  
  public String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new java.util.StringTokenizer(reader.readLine());
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }
  
  public int nextInt() {
    return Integer.parseInt(next());
  }
  
  public long nextLong() {
    return Long.parseLong(next());
  }
  
  public double nextDouble() {
    return Double.parseDouble(next());
  }
  
  public String[] next(int n) {
    String[] array = new String[n];
    for (int i = 0; i < n; i++) {
      array[i] = next();
    }
    return array;
  }
  
  public int[] nextInt(int n) {
    int[] array = new int[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextInt();
    }
    return array;
  }
  
  public long[] nextLong(int n) {
    long[] array = new long[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextLong();
    }
    return array;
  }
  
  public double[] nextDouble(int n) {
    double[] array = new double[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextDouble();
    }
    return array;
  }
  
  public char[] nextCharArray() {
    return next().toCharArray();
  }
  
  public int[][] nextInt(int n, int m) {
    int[][] matrix = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextInt();
      }
    }
    return matrix;
  }
  
  public long[][] nextLong(int n, int m) {
    long[][] matrix = new long[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextLong();
      }
    }
    return matrix;
  }
  
  public double[][] nextDouble(int n, int m) {
    double[][] matrix = new double[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextDouble();
      }
    }
    return matrix;
  }
  
  public char[][] nextCharArray(int n) {
    char[][] matrix = new char[n][];
    for (int i = 0; i < n; i++) {
      matrix[i] = next().toCharArray();
    }
    return matrix;
  }
}


Measured memory_bytes: 21844
#include<stdio.h>

void swap(int *nx, int *ny)
{
    int temp = *nx;
    *nx = *ny;
    *ny = temp;
}


void sort3(int *n1, int *n2, int *n3)
{
    if (*n1 > *n2) swap(n1, n2);
    if (*n2 > *n3) swap(n2, n3);
    if (*n1 > *n2) swap(n1, n2);
}

int main(void){
 
int a,b,c,n;
 
scanf("%d%d%d",&a,&b,&c);

   sort3(&a, &b, &c);
 
if((b - a) % 2 == 0)  n = (b - a)/2 + (c - b);
else n = (b+1-a)/2 + (c - b) + 1;

printf("%d",n);

return 0;
 
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
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; }
const long long INF = 1LL << 60;
 
typedef pair<ll,ll> pairs;
vector<pairs> p;
bool pairCompare(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.first < secondElof.first;
}
#define MAX_N 1000100
bool x[MAX_N];
ll num[MAX_N];
ll fibl[MAX_N]={0};
 
ll fib(ll a){
    if (fibl[a]!=0)return fibl[a];
    if (a==0){
        return 0;
    }else if (a==1){
        return 1;
    }
    return fibl[a]=fib(a-1)+fib(a-2);
}
 
ll eratosthenes(ll n) {
    int p = 0;
    for (ll i=0; i<=n; ++i) x[i] = true;
    x[0] = x[1] = false;
    for(int i=2; i<=n; ++i) {
        if(x[i]) {
            p++;
            for(int j=2*i; j<=n; j+=i) x[j] = false;
        }
        
        num[i] = p;
    }
    return p;
}
 
ll gcd(ll a,ll b){
    if (a%b==0)return(b);
    else return(gcd(b,a%b));
}
 
ll keta(ll N){
    int tmp{};
    while( N > 0 ){
        tmp += ( N % 10 );
        N /= 10;
    }
    N = tmp;
    return N;
}

int main(){
    ll p,q,r;
    cin >> p >> q >> r;
    
    cout << min({p+q, q+r, r+p}) << endl;
    
    
    return 0;
}



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

int main() {
  int N;
  cin >> N;
  
  vector<int> a(N);
  
  for (int i = 0; i < N; i++) {
    cin >> a.at(i);
  }
  
  int num = 0;
  int now_blink = 1;
  int i = 0;
  while (i < 100000) {
    now_blink = a.at(now_blink - 1);
    num++;
    if (now_blink == 2) {
      cout << num << endl;
      return 0;
    }
    i++;
  }
  
  if (i >= 100000)
    cout << -1 << endl;
}

Measured memory_bytes: 640
import itertools


n = int(input())

def calculate(n,length):
    count = 0
    for i in itertools.product([3,5,7],repeat=length):
        if isValid(i) == False:
            continue
        sum = 0
        for j in range(length):
            sum = sum + i[j] * 10 ** j
        if sum <= n:
            count = count + 1

    return count

def isValid(n):
    dict = {}
    for s in n:
        if dict.get(s) == None:
            dict.__setitem__(s,1)
        else:
            dict.__setitem__(s,dict.get(s) + 1)

    s1 = dict.get(3) != None and dict.get(3) > 0
    s2 = dict.get(5) != None and dict.get(5) > 0
    s3 = dict.get(7) != None and dict.get(7) > 0

    return s1 and s2 and s3

length = len(str(n))

result = 0
for i in range(3,length+1):
    result = result + calculate(n,i)

print(result)



Measured memory_bytes: 3064
import itertools
n=str(input())
ans=0
for i in range(3,len(n)+1):
    for j in itertools.product([3,5,7], repeat=i):
        if (3 not in j) or (5 not in j) or (7 not in j):
            continue
        a=''.join(list(map(str,j)))
        if int(a)<=int(n):
            ans+=1
print(ans)

    

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=1000000007,MAX=200005,INF=1<<30;

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int H,W,K;cin>>H>>W>>K;
    
    vector<string> S(H);
    for(int i=0;i<H;i++) cin>>S[i];
    
    int ans=0;
    
    for(int bit=0;bit<(1<<H);bit++){
        for(int bit2=0;bit2<(1<<W);bit2++){
            vector<string> T=S;
            for(int i=0;i<H;i++){
                if(bit&(1<<i)){
                    for(int j=0;j<W;j++) T[i][j]='.';
                }
            }
            for(int j=0;j<W;j++){
                if(bit2&(1<<j)){
                    for(int i=0;i<H;i++) T[i][j]='.';
                }
            }
            
            int cnt=0;
            for(int i=0;i<H;i++){
                for(int j=0;j<W;j++){
                    if(T[i][j]=='#') cnt++;
                }
            }
            
            if(cnt==K) ans++;
        }
    }
    
    cout<<ans<<endl;
}


Measured memory_bytes: 3660
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int q = sc.nextInt();
        int cnt = 1;
        List<Character> str = new ArrayList<>();
        for(int i = 0; i < s.length(); i++){
            str.add(s.charAt(i));
        }
        while(cnt <= q){
            String order = sc.next();
            int a = sc.nextInt();
            int b = sc.nextInt();
            char k =0;
            char l = 0;
            int a2 = 0;
            int b2 = 0;
            if(order.equals("print")){
                for(int i = 0; i <= b - a; i++){
                    System.out.print(str.get(i + a));
                }
                System.out.println("");
            }else if(order.equals("reverse")){
                 a2 = a;
                    b2 = b;
                for(int i = 0; i < (b - a)/2+((b - a)%2); i++){
                   k = str.get(a2);
                   l = str.get(b2);
                           str.set(a2, l);
                           str.set(b2, k);
                           a2++;
                           b2--;
                }
            }else{
            String p = sc.next();
            a2 = a;
            for(int i = 0; i <= b - a; i++){
                str.set(a2, p.charAt(i));
                a2++;
            }
        }
            cnt++;
        }
    }}

Measured memory_bytes: 33432
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
constexpr Int mod = 1e9 + 7;
template <class T> T modpow(T a, T b) {
    if (b == 0) return T(1);
    if (b % 2 == 0) {
        long long d = modpow(a, b / T(2));
        return (d * d) % mod;
    } else {
        return (a * modpow(a, b - 1) % mod );
    }
}
template<class T> T mod_nCr(T n, T r, T mod ) {
    T denom = 1;
    T numer = 1;
    for (T i = 1; i <= r; i++) numer = (numer * i) % mod;
    for (T i = n - r + 1; i <= n; i++) denom = (denom * i) % mod;
    return (denom * modpow(numer, mod - 2) % mod);
}
void solve(){
    Int N,a,b; cin >> N >> a >> b;
    Int res  = modpow(2LL,N) - 1;
    Int remu = mod_nCr(N,a,mod);
    Int ramu = mod_nCr(N,b,mod);
    res -= remu; res += mod;res %= mod; res -= ramu; res += mod; res %= mod;
    cout << res << endl;
    
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int Q = 1;
    while (Q--) { solve();}
}


Measured memory_bytes: 3624
from math import floor,ceil,sqrt
import fractions
from collections import deque
import itertools
from collections import deque
import heapq
N,M=map(int,input().split())
tree=[[] for _ in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
d=[float("inf") for _ in range(N)]
d[0]=0
q=[]
prev=[-1]*N
q.append([0,0])
q1=q
flag=1
#print(q)
heapq.heapify(q)
#print(q1)
while len(q)>0:
    dist,u=heapq.heappop(q)
    if d[u]<dist: continue
    for i in tree[u]:
        alt=d[u]+1
        if d[i]>alt:
            d[i]=alt
            prev[i]=u
            heapq.heappush(q,[alt,i])
    #print(prev,d,q1)
for i in range(1,N):
    if prev[i]==-1:
        flag=0
        break
if flag==0:
    print("No")
else:
    print("Yes")
    for i in range(1,N):
        print(prev[i]+1)





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

using namespace std;
#define ll long long
#define pb push_back
#define vi vector<int>
#define vll vector<long long>
#define inf 1000000100
#define infll 1LL << 50

int main()
{
    ll h, w;
    cin >> h >> w;
    ll diff = infll;
    for(ll a = 1; a <= h-1; a++)
    {
        if(a < h-1)
        {
        ll recta = a*w;
        ll rectb = ((h-a)/2)*w;
        ll rectc = h*w - recta - rectb;
        diff = min(diff, max(recta, max(rectb, rectc)) - min(recta, min(rectb, rectc)));

        rectb = (h-a)*(w/2);
        rectc = h*w - recta - rectb;
        diff = min(diff, max(recta, max(rectb, rectc)) - min(recta, min(rectb, rectc)));
        }
        else
        {
            ll recta = a*w;
            ll rectb = (h-a)*(w/2);
            ll rectc = h*w - recta - rectb;
            diff = min(diff, max(recta, max(rectb, rectc)) - min(recta, min(rectb, rectc)));
        }
    }

    for(ll a = 1; a <= w-1; a++)
    {
        if(a < w - 1)
        {
        ll recta = a*h;
        ll rectb = ((w-a)/2)*h;
        ll rectc = h*w - recta - rectb;
        diff = min(diff, max(recta, max(rectb, rectc)) - min(recta, min(rectb, rectc)));

        rectb = (w-a)*(h/2);
        rectc = h*w - recta - rectb;
        diff = min(diff, max(recta, max(rectb, rectc)) - min(recta, min(rectb, rectc)));
        }
        else
        {
            ll recta = a*h;
            ll rectb = (w-a)*(h/2);
            ll rectc = h*w - recta - rectb;
            diff = min(diff, max(recta, max(rectb, rectc)) - min(recta, min(rectb, rectc)));
        }
    }

    cout << diff << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>

int main() {
  std::string data;

  while (std::cin >> data) {
    if (data == "-") {
      break;
    }
    int m;
    std::cin >> m;
    for (int i = 0; i < m; i++)
    {
      int h;
      std::string tmp;
      std::cin >> h;
      tmp = data.substr(0, h);
      data.erase(0, h);
      data += tmp;
    }
    std::cout << data << "\n";
  }
}


Measured memory_bytes: 3116
import sys
read = sys.stdin.buffer.read # 全読み込み
readline = sys.stdin.buffer.readline # 一行読み込み
readlines = sys.stdin.buffer.readlines # 一行ずつ全読み込み
sys.setrecursionlimit(10**7) # 再帰限界変更（デフォルトは1000）

"""
# 文字列（数値変換も含む）
n = readline().rstrip() # １行に１文字列のみ
lis = readline().rstrip().split() # # １行に複数の文字列

# 数値（文字変換も含む）
n = int(readline().rstrip()) # １行に数値１個のみ
a, b, c = map(int,readline().rstrip().split()) # １行に複数の数値
A = list(map(int,readline().rstrip().split()))  # １行に複数の数値（リスト受け取り）
lis = [readline().rstrip().split() for _ in range(n)] # １行に複数の数値(m個)かつ、n行続く場合（出力は二次元リスト：[['1', '2'], ['4', '5']]）

# dとAの行が交互に並んでいる場合
s = sys.stdin.readlines()
n, k=map(int, s[0].split())
d=[]
A=[]
for i in s[1:2*k:2]:
    d.append(int(i))
for i in s[2:2*k+1:2]:
    A.append(list(map(int, i.split())))
"""

a,b,c,d=map(int,readline().rstrip().split())

import fractions
f = fractions.gcd(c,d) # 最大公約数
f2 = c*d // f # 最小公倍数

# b以下で条件を満たす個数
shou1=b//c
shou2=b//d
shou3=b//f2
num_b=b-(shou1+shou2-shou3)

# a-1以下で条件を満たす個数
shou4=(a-1)//c
shou5=(a-1)//d
shou6=(a-1)//f2
num_a=(a-1)-(shou4+shou5-shou6)

print(num_b-num_a)

Measured memory_bytes: 5496
// -*- coding:utf-8-unix -*-

use proconio::input;

fn main() {
    input! {
        n: usize,
        m: usize,
        mut x: [i32; m],
    }

    if n >= m {
        println!("0");
        return;
    }

    x.sort();
    let mut v = Vec::with_capacity(m - 1);
    for i in 1..m {
        v.push((x[i] - x[i - 1]).abs());
    }
    v.sort();
    println!("{}", v.iter().take(m - n).sum::<i32>());
}


Measured memory_bytes: 3392
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <ios>
#include <string>
using namespace std;
int main(void){
  string s;
  cin >> s;
  
  int n = s.length();
  
  int zero = 0;
  int one = 0;
  
  for(int i=0;i<n;i++){
    if(s[i] == '0')
      zero++;
    else
      one++;
  }
  
  cout << min(zero,one) * 2 << endl;
  
  return 0;
}
    

Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
using namespace std;

int main() {
    string divide[4] = {"dream", "dreamer", "erase", "eraser"};
    string S;
    cin >> S;

    reverse(S.begin(), S.end());
    for (int i=0; i<4; ++i) reverse(divide[i].begin(), divide[i].end());

    bool isDiv = true;
    for (int i=0; i<S.size();){
        bool isDiv2 = false;
        for (int j=0; j<4; ++j){
            string d = divide[j];
            if (S.substr(i, d.size()) == d){
                isDiv2 = true;
                i += d.size();
            }
        }
        if (!isDiv2) {
            isDiv = false;
            break;
        }
    }

    if (isDiv) cout << "YES" << endl;
    else cout << "NO" << endl;
}


Measured memory_bytes: 512
#include <stdio.h>

int main(int argc, const char * argv[])
{

    int a, b, y, cnt = 0;
    
    while(1) {
        scanf("%d %d", &a, &b);
        if (a == 0 && b == 0) {
            break;
        } else {
            if (cnt != 0) {
                printf("\n");
                cnt = 0;
            }
            for (y = a; y <= b; y++) {
                if ((y % 400 == 0) || (y % 4 == 0 && y % 100 != 0)) {
                    printf("%d\n", y);
                    cnt++;
                }
            }
            if (cnt == 0) {
                printf("NA\n");
                cnt++;
            }
        }
    }
    
    return 0;
}

Measured memory_bytes: 612
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef pair<double,double> pdd;
#define MEM(a, b) memset(a, (b), sizeof(a))
#define SZ(i) ll(i.size())
#define FOR(i, j, k, in) for (ll i=j ; i<k ; i+=in)
#define RFOR(i, j, k, in) for (ll i=j ; i>=k ; i-=in)
#define REP(i, j) FOR(i, 0, j, 1)
#define REP1(i,j) FOR(i, 1, j+1, 1)
#define RREP(i, j) RFOR(i, j, 0, 1)
#define ALL(_a) _a.begin(),_a.end()
#define mp make_pair
#define pb push_back
#define X first
#define Y second
#ifdef tmd
#define debug(...) do{\
    fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
    _do(__VA_ARGS__);\
}while(0)
template<typename T>void _do(T &&_x){cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x,S &&..._t){cerr<<_x<<" ,";_do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s,const pair<_a,_b> &_p){return _s<<"("<<_p.X<<","<<_p.Y<<")";}
template<typename It> ostream& _OUTC(ostream &_s,It _ita,It _itb)
{
    _s<<"{";
    for(It _it=_ita;_it!=_itb;_it++)
    {
        _s<<(_it==_ita?"":",")<<*_it;
    }
    _s<<"}";
    return _s;
}
template<typename _a> ostream &operator << (ostream &_s,vector<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,set<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s,map<_a,_b> &_c){return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
#else
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)
#endif

template<class T> inline bool cmax(T &a, const T &b) { return b > a ? a = b, true : false; }
template<class T> inline bool cmin(T &a, const T &b) { return b < a ? a = b, true : false; }
template<class T> using MaxHeap = priority_queue<T>;
template<class T> using MinHeap = priority_queue<T, vector<T>, greater<T>>;

const ll MOD=1000000007;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll MAXN=1e5+5;
const ll MAXLG=__lg(MAXN)+2;

ll a,b,k;
/********** Main()  function **********/
int main()
{
  IOS();
  cin>>a>>b>>k;
  REP(i,k){
    if(i&1){
      if(b&1)b--;

      a += b/2;
      b /= 2;

    } else {
      if(a&1)a--;

      b += a/2;
      a /= 2;

    }
  }

  cout<<a<<" "<<b<<endl;

  return 0;
}


Measured memory_bytes: 256
(defun count-char (str chr)
  (loop :for x :across str
        :count (char= x chr)))

(defun solve (str)
  (if
   (<= 8 (+ (- 15 (length str)) (count-char str #\o)))
   "YES"
   "NO"))

(defun main ()
  (format t "~A~%" (solve (read-line))))

(main)


Measured memory_bytes: 14176
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }

/*
 <url:http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0001>
 問題文============================================================
 =================================================================
 解説=============================================================
 やるだけ
 ================================================================
 */
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    priority_queue<int> pq;
    for(int i = 0; i < 10;i++){
        int h; cin >> h; pq.push(h);
    }
    for(int i = 0; i < 3;i++){
        cout << pq.top() << endl;
        pq.pop();
    }
    return 0;
}



Measured memory_bytes: 3132
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int dp[2005],n,k;
int qpow(int x,int y)
{
	if(y<0)return 1;
	int res=1;
	while(y)
	{
		if(y&1)res=res*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return res;
}
signed main()
{
	cin>>n>>k;
	dp[0]=1;
	for(int i=1;i<n;++i)
	{
		for(int j=i;j>=1;--j)
		{
			dp[j]=dp[j+1]+dp[j-1];
			if(dp[j]>=mod)dp[j]-=mod;
		}
		dp[0]=dp[1];
	}
	cout<<dp[n-k]*qpow(2,n-k-1)%mod<<endl;
}


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

ll inf=1e18;

int main() {
  ll n,m;
  cin >> n >> m;
  vector<ll> d(n,inf);
  d[0]=0;
  vector<map<ll,ll>> e(n);
  for(ll i=0;i<m;i++) {
    ll a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    e[a][b]=-c;
  }
  
  for(ll loop=0;loop<n-1;loop++) {
    bool update=false;
    for(ll i=0;i<n;i++) {
      if(d[i]!=inf) {
        for(auto p:e[i]) {
          ll to=p.first;
          ll v=p.second;
          if(d[to]>d[i]+v) {
            d[to]=d[i]+v;
            update=true;
          }
        }
      }
    }
    if(!update) {
      break;
    }
  }
  vector<bool> neg(n,false);
  for(ll loop=0;loop<n;loop++) {
    bool update=false;
    for(ll i=0;i<n;i++) {
      if(d[i]!=inf) {
        for(auto p:e[i]) {
          ll to=p.first;
          ll v=p.second;
          if(d[to]>d[i]+v) {
            d[to]=d[i]+v;
            update=true;
            neg[to]=true;
          }
          if(neg[i]) {
            neg[to]=true;
          }
        }
      }
    }
    if(!update) {
      break;
    }
  }
  if(neg[n-1]) {
    cout << "inf" << endl;
  }
  else {
    cout << -d[n-1] << endl;
  }
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <string>
#include <stack>
#include <iomanip>
#include <numeric>
#include <queue>
#include <climits>
#include <complex>
#include <cmath>
#include <map>
using namespace std;
using ll = long long;
#define MOD 1000000007
#define INF 1LL << 59

int arr[4];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    //cout << fixed << setprecision(3);
    int n;
    char buf[10];
    while (scanf("%d,%s", &n, buf) != EOF)
    {
        if (buf[0] == 'A' && buf[1] == 'B')
            arr[3]++;
        else if (buf[0] == 'A')
            arr[0]++;
        else if (buf[0] == 'B')
            arr[1]++;
        else if (buf[0] == 'O')
            arr[2]++;
    }

    cout << arr[0] << "\n"
         << arr[1] << "\n"
         << arr[3] << "\n"
         << arr[2] << endl;
    return 0;
}


Measured memory_bytes: 3192
N = int(input())

def dfs(s):
  if int(s) > N:
    return 0
  # s 自体が七五三数なら +1
  if all(s.count(c) > 0 for c in '753'):
    ret = 1
  else:
    ret = 0 
  for c in '753':
    ret += dfs(s + c)
  return ret

print(dfs('0'))

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

int main(){
	vector<int> S(13,0);
  vector<int> H(13,0);
  vector<int> C(13,0);
  vector<int> D(13,0);
	int n;
	char c; int num;
	cin >> n;

	for(int i=0; i<n; i++){
		cin >> c >> num;
		switch(c){
			case 'S':
				S[num-1] = 1; break;
			case 'H':
				H[num-1] = 1; break;
			case 'C':
				C[num-1] = 1; break;
			case 'D':
				D[num-1] = 1; break;
		}
	}

	for(int i=0; i<13; i++){
		if(S[i] == 0) { n=i+1; cout << "S" << " " <<n << endl ;}
	}
	for(int i=0; i<13; i++){
		if(H[i] == 0) { n=i+1; cout << "H" << " " << n<< endl ;}
	}
	for(int i=0; i<13; i++){
		if(C[i] == 0) { n=i+1; cout << "C" << " " << n<< endl ;}
	}
	for(int i=0; i<13; i++){
		if(D[i] == 0) { n=i+1; cout << "D" << " " <<n<< endl;}
	}

}

Measured memory_bytes: 3052
var input = '';
process.stdin.resume();
process.stdin.setEncoding('utf8');
process.stdin.on('data', function(chunk) {
    input += chunk;
});
process.stdin.on('end', function() {
    main(input)
});

function main(input){
    var args = input.trim().split('\n');

    var i = 0;
    while(true) {
        var islandCount = parseInt(args[i++]);
        if(isEndInput(islandCount)) break;

        var islands = {};
        for(var j = 1; j <= islandCount; j += 1){
            islands[j] = {};
        }

        var sum = 0;
        for(var j = 0; j < islandCount - 1; j += 1){
            var bridgeData = splitNum(args[i++]);
            var a = bridgeData[0], b = bridgeData[1], cost = bridgeData[2];
            islands[a][b] = islands[b][a] = cost;
            sum += cost;
        }

        var cost = calcCost('1', null, islands);

        var res = (sum - cost.leafCost) * 2 - cost.maxCost;

        console.log(res);

    }
}

function calcCost(current, parent, islands){

    var island = islands[current];

    var isLeaf = true;
    var maxCost = 0;
    var leafCost = 0;
    for(var next in island){
        if(next === parent){ continue; }

        isLeaf = false;
        var childCost = calcCost(next, current, islands);
        leafCost += childCost.leafCost;
        var cost = island[next] + childCost.maxCost;

        if(cost > maxCost){
            maxCost = cost;
        }
    }

    if(isLeaf){
        leafCost += island[parent];
        maxCost -= island[parent];
    }
    return { maxCost : maxCost, leafCost : leafCost };
}

function splitNum(str){
    return str.split(' ').map(Number);
}

function isEndInput(arg){
    return arg === 0;
}

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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << fixed << setprecision(15);

  int n;
  string s;
  cin >> n >> s;

  int cnt = 0;
  for (int i = 0; i < 1000; i++) {
    int c[3] = {i / 100, (i / 10) % 10, i % 10};
    int f = 0;
    for (int j = 0; j < n; j++) {
      if ((s[j] - '0') == c[f]) f++;
      if (f == 3) break;
    }
    if (f == 3) cnt++;
  }
  cout << cnt << '\n';

  return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
template <class T1, class T2>void print(T1 a[], T2 n) { for (T2 i = 0; i < n; i++) { cout << a[i] << " ";} cout << endl;}
template <class T1, class T2>void print(vector<T1> a, T2 n) { for (T2 i = 0; i < n; i++) { cout << a[i] << " "; } cout << endl;}



int main() {
/*
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif
*/


  double r;
  cin >> r;
  cout << fixed << setprecision(20) << (2 * 3.141592653589793238462643383279 * r) << endl;
}

Measured memory_bytes: 3784
//INCLUDE
//------------------------------------------
#include <bits/stdc++.h>
//DEFINE
//------------------------------------------
#define ll long long
#define ld long double
#define ALLv(a)  (a).begin(),(a).end()
#define ALL(a,n)  (a),(a)+n
#define vi vector<long long>
#define vd vector<long double>
#define vs vector<string>
//CONST
//------------------------------------------
#define INF 1010000000000000017LL
#define MOD 1000000007LL
#define EPS 1e-12
#define PI 3.14159265358979323846
//REPEAT
//------------------------------------------
#define   FOR(i,m,n) for(ll (i)=(m);   (i)<(n);  (i)++)
#define   REP(i,n)   for(ll (i)=0;     (i)<(n);  (i)++)
#define  REPS(i,x)   for(ll (i)=1;     (i)<=(x); (i)++)
#define  RREP(i,x)   for(ll (i)=(x)-1; (i)>=0;   (i)--)
#define RREPS(i,x)   for(ll (i)=(x);   (i)> 0;   (i)--)
#define  WREP(i,in,j,jn) REP(i,in)REP(j,jn)
//-----------------------------------------
#define ifYN(x) cout<<(x?"Yes":"No")<<"\n" 
#define dcml(n) fixed<<setprecision(n)

 
ll GCD(ll a,ll b) { return b ? GCD(b,a%b) : a; } 
ll LCM(ll a,ll b) { return a/GCD(a,b)*b; } 
ll Factorial(ll n){ ll m=1;while(n>=1)m*=n--;return m; } 
ll modPow(ll x,ll n,ll mod=MOD){ 
    return (!n?1:!n%2?modPow(x*x,n/2,mod)%mod:x%mod*modPow(x,n-1,mod)%mod); 
} 
ll GetDigit(ll num){ 
    ll digit=0; 
    while(num!=0){num/=10;digit++;} 
    return digit; 
} 


using namespace std;
//-------------------------------------------
const ll MAX_N=300;
typedef pair<ll,ll> P;
struct Edge{
  ll to,dist;
};
ll N;

int main(){
  ll N,M,L;cin>>N>>M>>L;
  
  ll d[MAX_N][MAX_N];
  WREP(i,N,j,N)d[i][j]=INF;REP(i,N)d[i][i]=0;
  ll a,b,c;
  REP(i,M){
    cin>>a>>b>>c;
    a--;b--;
    d[a][b]=d[b][a]=c;
  }
  //wawawa!!!
  REP(k,N){
    REP(i,N){
      REP(j,N){
        d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
      }
    }
  }
  //REP(i,N){REP(j,N)cout<<d[i][j]<<" ";cout<<"\n";}
  
  ll d2[MAX_N][MAX_N];
  WREP(i,N,j,N)d2[i][j]=INF;REP(i,N)d2[i][i]=0;
  REP(i,N){
    FOR(j,i,N){
      if(d[i][j]<=L){
          d2[i][j]=d2[j][i]=1;
      }
    }
  }
  //wawawa!!!
  REP(k,N){
    REP(i,N){
      REP(j,N){
        d2[i][j]=min(d2[i][j],d2[i][k]+d2[k][j]);
      }
    }
  }
  //REP(i,N){REP(j,N)cout<<d[i][j]<<" ";cout<<"\n";}
  ll Q;cin>>Q;
  ll s,t;
  REP(i,Q){
    cin>>s>>t;
    s--;t--;
    cout<<(d2[s][t]>=INF/10?-1:d2[s][t]-1)<<"\n";
  }
}


Measured memory_bytes: 1920
import string

C=string.ascii_lowercase

L=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

try:
    while True:
        A=input()
        
        if(A):
            A=A.lower()
            for i in range(26):
                B=A.count(C[i])
                L[i]+=B
                i+=1
            
        
        
        
except EOFError:
    pass

for j in range(26):
            print(C[j],end='')
            print(' : ',end='')
            print(L[j])
            j+=1
        


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

int main(){
    int w,h,n;
    std::cin >> h >> w >> n;
    if(w > h){
        std::cout << std::ceil( n / (double)w) << std::endl;
    }else{
        std::cout << std::ceil( n / (double)h) << std::endl;
    }
}

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

public class Main {
	void run() {
		Scanner sc = new Scanner(System.in);
		long x = sc.nextLong();
		long n = x * 2 / 11 + 1;
		if(x < 6) {
			System.out.println(1);
		}
		else if(11 * (n - 2) / 2 + 6 >= x) {
			System.out.println(n-1);
		}else {
			System.out.println(n);
		}
		sc.close();
	}

	void debug(Object... o) {
		System.out.println(Arrays.deepToString(o));
	}

	public static void main(String[] args) {
		new Main().run();
	}
}


Measured memory_bytes: 21716
#include<iostream>
#include<string>
#include<cmath>
//#include<array>
#include<algorithm>
//#include<deque>
#include<vector>
//#include<utility>
#include<set>
//#include<map>
//#include<list>

using namespace std;

//class UnionFind {
//public:
//	vector<int>data;
//	UnionFind(int size) :data(size, -1) {};
//	bool unionset(int x, int y) {
//		x = root(x), y = root(y);
//		if (x != y) {
//			if (data[y] < data[x]) {
//				swap(x, y);
//			}
//			data[x] += data[y];
//			data[y] = x;
//		}
//		return x != y;
//	}
//	bool findset(int x, int y) {
//		return root(x) == root(y);
//	}
//	int root(int x) {
//		return data[x] < 0 ? x : data[x] = root(data[x]);
//	}
//	int size(int x) {
//		return -data[root(x)];
//	}
//};

//int gcd(int x, int y) {
//	int tmp, r;
//	if (x < y) {
//		tmp = x;
//		x = y;
//		y = tmp;
//	}
//	r = x % y;
//	while (r != 0) {
//		x = y;
//		y = r;
//		r = x % y;
//	}
//	return y;
//}

int main(void) {
	int N;
	long double res = 0, a;
	vector<long double>vec1;
	vector<string>vec2;
	string str;
	cin >> N;
	for (int i = 0; i < N;i++) {
		cin >> a >> str;
		vec1.push_back(a);
		vec2.push_back(str);
	}
	for (int i = 0; i < N;i++) {
		if (vec2[i] == "JPY") {
			res += vec1[i];
		}
		else {
			res += vec1[i] * 380000;
		}
	}
	cout << res << endl;
}

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

int main() {
  int y;
  int x;
  cin >> y >> x;
  vector<string> vec(y+2);
  char c='#';
  string s;
  string t;
  
  for( int j = 0 ; j < x+2 ; j++ ){
    s += c;
  }
  
  for( int i = 0 ; i < y+2 ; i++ ){
    if (i == 0 || i == y+1){
      vec.at(i)=s;
    }
    else{
      cin >> t;
      vec.at(i) = "#" + t + "#";
    }
  }
  
  for( int k = 0 ; k < y+2 ; k++ ){
    cout << vec.at(k) << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include<algorithm>
#include<vector>
using namespace std;
using ll = long long;
#define INF 1e9
int main() {
    ll X, Y;
    cin >> X >> Y;
    ll ans = 0;
    for (ll i = 0; i < INF; ++i) {
        if (X <= Y) {
            ans++;
        }
        else {
            break;
        }
        X *= 2;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define ll int64_t
#define all(v) v.begin(), v.end()
#define bitrep(n) for(int bit=0;bit<(1<<n);bit++)

//列と行のうち、何個のボタンを押すかで考える。
//N行のうちi個、M行のうちj個のボタンを押した場合、黒いマスはi*(M-j)+j*(N-i)となる

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

  bool can=false;
  for(int i=0;i<=N;i++){
    for(int j=0;j<=M;j++){
       if(i*(M-j)+j*(N-i)==K) can=true; 
    }
  }
   if(can) cout << "Yes" << endl;
   else cout << "No" << endl;
      
  return 0;
}

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

int main(){
    int n;
    cin>>n;
    long long a[n];
    bool zero=false;
    int now=0;
    for (int i = 0; i < n; i++)
    {
        cin>>a[i];
        if(a[i]-now>1){
            cout<<-1<<endl;
            return 0;
        }
        now=a[i];
    }
    if(a[0]!=0){
        cout<<-1<<endl;
        return 0;
    }
    long long ans=0;
    reverse(a,a+n);

    now=-1;
    for(int i=0;i<n;i++){
        if(now-1!=a[i]){
            ans+=a[i];
            now=a[i];
        }
        else{
            now=a[i];
        }
    }
    cout<<ans<<endl;
    
    
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define r(i,n) for(int i=0;i<n;i++)
typedef pair<int,int>P;
#define fi first
#define se second
#define mk make_pair
int a[26];
main(){
	int h,w;
	cin>>h>>w;
	int s1=h,s2=w,p=(h/2)*(w/2);
	string s[h];
	r(i,h)cin>>s[i];
	r(i,h)r(j,w)a[s[i][j]-'a']++;
	while(p>0){
		int c=0;
		r(i,26){//cout<<a[i]<<endl;
			if(a[i]>=4){
				p--;
				a[i]-=4;
				c++;
				break;
			}
		}
	    if(!c){
	    	cout<<"No"<<endl;
	    	return 0;
	    }
	}
	if((h*w)%2)r(i,26){
		if(a[i]%2){
			a[i]--;
			break;
		}
	}
	r(i,26)if(a[i]%2){
		cout<<"No"<<endl;
		return 0;
	}
	cout<<"Yes"<<endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
 
int main(){
    //recieve inputs
    int N, X, T;
    cin >> N >> X >> T;
 
    //find the number of times to use the machine
    int times = (N + X - 1) / X;
 
    //find the answer
    int ans = times * T;
 
    //output the answer
    cout << ans << endl;
}


Measured memory_bytes: 3184
#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<algorithm>
#include<map>
#include<set>
#include<cmath>
#include<cassert>
#include<queue>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;

int A[100100];
int cnt[100100];

int main() {
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> A[i];
	for (int i = 0; i < N; i++)
		cnt[A[i]]++;
	const int MAX = 100100;
	int odd = 0, even = 0;
	for (int i = 0; i < MAX; i++) if (cnt[i]) {
		if (cnt[i]%2 == 0) even++;
		else odd++;
	}
	int ans = even+odd - (even%2==1);
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1024
N = int(input())
A = list(map(int, input().split()))
ans = 1
A.sort()
if A[0] == 0:
    print(0)
else:
    for i in range(N):
        ans *= A[i]
        if ans > 10**18:
            print(-1)
            exit(0)
    print(ans)


Measured memory_bytes: 21576
n,m = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(n)]
c = [list(map(int,input().split())) for _ in range(m)]


ans = [0] * n
for i in range(n):
    tmp = [0, 10 ** 18]
    for j in range(m):
        if abs(a[i][0]-c[j][0])+abs(a[i][1]-c[j][1]) < tmp[1]:
            tmp = [j,abs(a[i][0]-c[j][0])+abs(a[i][1]-c[j][1])]
    ans[i] = tmp[0]+1

for i in ans:
    print(i)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
const ll MOD = 1e9 + 7;
const int INF = 1e9;

int dis[90001];

int main() {
  int h, w, d;
  cin >> h >> w >> d;
  P mp[h * w + 1];
  for (int i = 1; i <= h; i++) {
    for (int j = 1; j <= w; j++) {
      int a;
      cin >> a;
      mp[a] = make_pair(i, j);
    }
  }
  for (int i = 1 + d; i <= h * w; i++) {
    dis[i] = abs(mp[i].first - mp[i - d].first) + abs(mp[i].second - mp[i - d].second);
    dis[i] += dis[i - d];
  }
  int q;
  cin >> q;
  while (q--) {
    int l, r;
    cin >> l >> r;
    cout << dis[r] - dis[l] << endl;
  }
  return 0;
}


Measured memory_bytes: 2176
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> pll;
#define mod 1000000007
#define all(x) (x).begin(), (x).end()
#define call(x) (x).cbegin(), (x).cend()
#define pb push_back
const long double PI = acos(-1);
const long long INF = (1 << 30);
ll gcd(ll a,ll b){return b ? gcd(b,a%b) : a;}
ll lcm(ll a,ll b){return a / gcd(a,b) * b;}
ll stringcount(string s, char c){return count(s.cbegin(), s.cend(), c);}
bool isInteger(double x){return floor(x) == x;}
ll ceil(const ll a, const ll b){return ((a)+(b)-1)/b;}


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

  string o, e;
  cin >> o >> e;
  char ans[o.size()+e.size()];
  for(ll i = 0; i < o.size(); i++){
    ans[i*2] = o[i];
  }
  for(ll i = 0; i < e.size(); i++){
    ans[i*2+1] = e[i];
  }

  for(auto c : ans) cout << c;
  cout << endl;
  return 0;
}

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

int main()
{
    int N, M;
    cin >> N >> M;
    vector<string> A(N);
    for (int r = 0; r < N; r++)
    {
        cin >> A.at(r);
    }
    vector<string> B(M);
    for (int r = 0; r < M; r++)
    {
        cin >> B.at(r);
    }

    for (int ra = 0; ra < N - M + 1; ra++)
    {
        for (int ca = 0; ca < N - M + 1; ca++)
        {
            bool matched = true;
            for (int r = 0; r < M; r++)
            {
                for (int c = 0; c < M; c++)
                {
                    if (A.at(ra + r).at(ca + c) != B.at(r).at(c))
                    {
                        matched = false;
                        break;
                    }
                }
                if (!matched)
                {
                    break;
                }
            }
            if (matched)
            {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
}

Measured memory_bytes: 256
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <unordered_map>
#define INF 11111111
#define MAX_DIFF 160*80
using namespace std;

int A[88][88];
int B[88][88];

int dp[2][88][2*MAX_DIFF+2];

//int Solve(int x,int y,int diff,int H,int W) {
//
//    if (x == H && y == W)
//        return abs(diff);
//
//    if (dp[x][y].find(diff)!=dp[x][y].end())
//        return dp[x][y][diff];
//
//    int ans = INF;
//
//    if (x < H) {
//        ans = min(ans, Solve(x+1,y,diff+A[x+1][y]-B[x+1][y],H,W));
//        ans = min(ans, Solve(x+1,y,diff-A[x+1][y]+B[x+1][y],H,W));
//    }
//    if (y < W) {
//        ans = min(ans, Solve(x,y+1,diff+A[x][y+1]-B[x][y+1],H,W));
//        ans = min(ans, Solve(x,y+1,diff-A[x][y+1]+B[x][y+1],H,W));
//    }
//    return dp[x][y][diff]=ans;
//}

int Solve(int H,int W) {
    
    for(int x=H;x>=1;x--)
        for(int y=W;y>=1;y--)
            for(int diff=-MAX_DIFF;diff<=MAX_DIFF;diff++) {
                if (x == H && y == W) {
                    dp[x&1][y][diff+MAX_DIFF]=abs(diff);
                    continue;
                }
                
                int ans=INF;
                if (x < H) {
                    if (abs(diff+A[x+1][y]-B[x+1][y]) <= MAX_DIFF)
                        ans = min(ans, dp[(x+1)&1][y][diff+A[x+1][y]-B[x+1][y]+MAX_DIFF]);
                    if (abs(diff-A[x+1][y]+B[x+1][y]) <= MAX_DIFF)
                        ans = min(ans, dp[(x+1)&1][y][diff-A[x+1][y]+B[x+1][y]+MAX_DIFF]);
                }
                if (y < W) {
                    if (abs(diff+A[x][y+1]-B[x][y+1]) <= MAX_DIFF)
                        ans = min(ans, dp[x&1][y+1][diff+A[x][y+1]-B[x][y+1]+MAX_DIFF]);
                    if (abs(diff-A[x][y+1]+B[x][y+1]) <= MAX_DIFF)
                        ans = min(ans, dp[x&1][y+1][diff-A[x][y+1]+B[x][y+1]+MAX_DIFF]);
                }
                dp[x&1][y][diff+MAX_DIFF]=ans;
            }
    return dp[1][1][A[1][1]-B[1][1]+MAX_DIFF];
    
}


int main() {
    int H,W;
    cin>>H>>W;
    for(int i=1;i<=H;i++)
        for(int j=1;j<=W;j++) {
            cin>>A[i][j];
        }
    for(int i=1;i<=H;i++)
        for(int j=1;j<=W;j++) {
            cin>>B[i][j];
        }
    cout << Solve(H,W) << endl;
}


Measured memory_bytes: 17152
#include <cstdio>
#include <algorithm>

using namespace std;
using ll = long long;

#define Input(x) scanf("%lld",&x)

ll n, m;
ll sum[123456];

int main()
{
	Input(n);
	Input(m);
	fill(sum, sum + 123456, 0);
	ll from; Input(from);
	--from;
	for (int j = 0; j < m - 1; ++j)
	{
		ll to; Input(to);
		--to;
		ll p = min(from, to);
		ll q = max(from, to);
		++sum[p]; --sum[q];
		from = to;
	}
	for (int i = 1; i < n; ++i)
	{
		sum[i] += sum[i - 1];
	}
	ll answer = 0;
	for (int i = 0; i < n - 1; ++i)
	{
		ll a, b, c;
		Input(a);
		Input(b);
		Input(c);
		answer += min(a * sum[i], b * sum[i] + c);
	}
	printf("%lld\n", answer);
	return 0;
}

Measured memory_bytes: 3660
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;
typedef long long ll;
using namespace std;
const ll mod=1000000007,mod9=1000000009;
template <class T>inline T lcm(T a,T b){return (a*b/__gcd(a,b));}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin>>n;
    ll a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    ll num=0;
    for(int i=0;i<n;i++){
        if(i%2==0){
            num+=a[i];
        }
        else{
            num-=a[i];
        }
    }
    ll ans[n];
    ans[0]=num;
    for(int i=1;i<n;i++){
        ans[i]=(a[i-1]-ans[i-1]/2)*2;
    }
    for(int i=0;i<n;i++){
        cout << ans[i]<<" ";
    }
    cout << endl;
    return 0;
}




Measured memory_bytes: 2944
N,M = map(int,input().split())
A = list(map(int,input().split()))

ans = "Yes"
sum_M = sum(A)
an = 0
for i in range(len(A)):
    if A[i] >= sum_M/(4*M):
        an += 1
        
if an<M:
    ans = "No"

print(ans)
    

Measured memory_bytes: 3060
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <cctype>
using namespace std;
typedef long long lint;
#define cout cerr
#define ni (next_num<int>())
template<class T>inline T next_num(){
	T i=0;char c;
	while(!isdigit(c=getchar())&&c!='-');
	bool flag=c=='-';
	flag?c=getchar():0;
	while(i=i*10-'0'+c,isdigit(c=getchar()));
	return flag?-i:i;
}
template<class T1,class T2>inline void apmax(T1 &a,const T2 &b){if(a<b)a=b;}
template<class T1,class T2>inline void apmin(T1 &a,const T2 &b){if(b<a)a=b;}
const int N=100010;
namespace B{
	int c[N],n;
	inline void init(int _n){
		memset(c+1,0,(n=_n)<<2);
	}
	inline void add(int x,int v){
		for(;x<=n;c[x]+=v,x+=x&-x);
	}
	inline int sum(int x){
		int ans=0;
		for(;x;ans+=c[x],x^=x&-x);
		return ans;
	}
}
inline bool getrev(int a[],int n,int mx){
	B::init(mx);
	bool ans=0;
	for(int i=n-((n&1)^1);i>=1;i-=2){
		ans^=B::sum(a[i])&1;
		B::add(a[i],1);
	}
	return ans;
}
bool vis[N];
int a[3][N],b[N];
inline bool Main(){
	int n=ni;
	for(int i=0;i<3;i++){
		for(int j=1;j<=n;j++){
			a[i][j]=ni;
		}
	}
	memset(vis,0,sizeof(vis));
	bool revt[2]={false,false};
	for(int i=1;i<=n;i++){
		if(a[1][i]%3!=2)return false;
		b[i]=(a[1][i]+1)/3;
		if(vis[b[i]]||((i&1)!=(b[i]&1)))return false;
		vis[b[i]]=true;
		if(a[0][i]==a[1][i]-1&&a[2][i]==a[1][i]+1){
			revt[i&1]^=(((b[i]^i)>>1))&1;
		}else if(a[0][i]==a[1][i]+1&&a[2][i]==a[1][i]-1){
			revt[i&1]^=((((b[i]^i)>>1))&1)==0;
		}else return false;
	}
	revt[0]^=getrev(b,n,n);
	revt[1]^=getrev(b+1,n-1,n);
	return !revt[0]&&!revt[1];
}
int main(){
	puts(Main()?"Yes":"No");
	return 0;
}

Measured memory_bytes: 2304
#include <bits/stdc++.h>
using namespace std;
#define ll long long int

int main()
{
	ll n;
	cin>>n;
	vector<ll> a(n),b(n),c(n);
	for(ll i=0;i<n;i++)
		cin>>a[i];
	for(ll i=0;i<n;i++)
		cin>>b[i];
	for(ll i=0;i<n;i++)
		cin>>c[i];
	sort(a.begin(),a.end());
	sort(b.begin(),b.end());
	sort(c.begin(),c.end());
	
	ll ans=0;
	for(ll i=0;i<n;i++)
	{
		vector<ll>::iterator lower,upper;
    	lower = lower_bound (a.begin(), a.end(),b[i]);  
    	upper = upper_bound (c.begin(), c.end(),b[i]);
		ans+=(lower-a.begin())*(n-(upper-c.begin()));
	
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 5636
#include<iostream>
#include<algorithm>
#include<vector>
#include<numeric>
#include<string>
#include<cmath>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<iomanip>
#include<cctype>
#include<map>
#include<cstring>
#include<bitset>
#include<cassert>

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,a,b) for (int (i)=a;(i)<(b);(i)++)
#define all(x) (x).begin(),(x).end()

using namespace std;
using ll = long long int;

const int inf = 1001001000;
const long long int Inf = 1001001001001001000;



void print(vector<vector<int>> a){
	for (int i = 0; i < a.size(); i++)
	{
		for (int j=0;j<a[i].size();j++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
}

void print(vector<vector<long long int>> a){
	for (int i=0;i<a.size();i++){
		for (int j=0;j<a[i].size();j++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
}

void print(vector<int> a){
    int n = a.size();
    for (int j=0;j<n;j++) {
        if (j != n-1) cout << a[j] << " ";
        else cout << a[j] << endl;
    }
}

void print(vector<long long int> a){
    int n = a.size();
    for (int j=0;j<n;j++) {
        if (j != n-1) cout << a[j] << " ";
        else cout << a[j] << endl;
    }
}

void print(set<int> a){
	for (auto x:a)
		cout << x << " ";
	cout << endl;
}

int main()
{
	int n, k;
	cin >> n >> k;
	int ans = k;
	rep(i,n-1){
		ans *= (k-1);
	}
	cout << ans << endl;
	

	return 0;
}

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

using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef long double ld;
typedef vector<ld> vd;
typedef bool bl;
typedef vector<bl> vb;
typedef unordered_map<ll,unordered_map<ll,ll>> graph;

const ll e5 = 1 << 21;
const ll mod = 1000000007;
const ll e3 = 1 << 13;
const int INF = 1 << 30;

string s;
int dp[1 << 26];

int main(){
  cin >> s;
  ll bit = 0;
  fill(dp,dp+(1<<26),INF);
  dp[0] = 0;
  for(char c : s){
    bit ^= (1 << c-'a');
    int m = INF;
    for(ll i = 0;i < 26;i++){
      m = min(m,dp[(bit^(1 << i))]);
    }
    dp[bit] = min(dp[bit],m+1);
  }
  cout << max(1,dp[bit]) << endl;

}


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

int main() {
 string str;
  int count, i;
  count = 0;
  cin >> str;
    for (i = 0; i < 4; i++) {
         if (str.at(i) == '2') {
              count++;
   }
      }
  cout << count <<endl;
}



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

using namespace std;

int main()
{
	int n, W;
	cin >> n >> W;
	long long v[n];
	int w[n];
	for(int i=0;i<n;i++)
		cin >> w[i] >> v[i];
	long long dp[W+1];
	memset(dp, 0, sizeof(dp));
	for(int i=0;i<n;i++)
	{
		for(int j=W;j>=0;j--)
		{
			if(j-w[i] >= 0)
				dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
		}
	
	}
	long long ans = 0;
	for(int i=0;i<=W;i++)
	{
		ans = max(ans, dp[i]);
	}
	cout << ans << "\n";
	return 0;
}


Measured memory_bytes: 1024