akhauriyash/Code-Regression huggingface dataset:
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class Main {
    public static void main(String args[]){
        Scanner scanner = new Scanner(System.in);
        int l = scanner.nextInt();
        int is[] = new int[l];
        for (int i = 0;i < l;++i){
            is[i] = scanner.nextInt();
        }
        int j = 0,k,alr = 0;
        HashMap<Integer,Integer> counter = new HashMap<>();
        for (int i = 0;i < l;++i){
            counter.put(is[i],counter.containsKey(is[i]) ? counter.get(is[i]) + 1 : 1);
        }
        for (int key:counter.keySet()){
            if(counter.get(key) > key){
                alr += counter.get(key) - key;
            }
            else if(counter.get(key) < key){
                alr += counter.get(key);
            }
        }
        System.out.println(alr);
    }
}

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


int main()
{
	int A1, A2, A3;
	cin >> A1 >> A2 >> A3;

	int B = A1 + A2 + A3;
	if (B >= 22) {
		cout << "bust" << endl;
	}
	else {
		cout << "win" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll MOD=1e9+7;
const ll MOD2=1e9+9;
const ll N=2e5+5;
const ld pi=3.14159265359;
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(a) (ll)a.size()

ll n,m,x,y,ans;
vector<ll> v[N];
multiset<ll,greater<ll> > s;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);	
	cin>>n>>m;
	REP(i,n){
		cin>>x>>y;
		v[x].pb(y);
	}
	for(ll i=1;i<=m;i++){
		for(ll j:v[i])s.insert(j);
		if(SZ(s)){
			ans+=*s.begin();
			s.erase(s.begin());
		}
	}
	cout<<ans<<"\n";
	return 0;
}




Measured memory_bytes: 10624
import sys
sys.setrecursionlimit(10**8)

INF = 10**8

def rec(x, memo):
    if x == 0: return 0
    if memo[x] != -1: 
        return memo[x]
    
    res = INF
    pow6 = 1
    while x - pow6 >= 0:
        res = min(res, rec(x-pow6, memo)+1)
        pow6*=6
    
    pow9 = 1
    while x - pow9 >= 0:
        res = min(res, rec(x-pow9, memo)+1)
        pow9*=9

    memo[x] = res
    return res

n = int(input())
memo = [-1]*(n+1)
print(rec(n, memo))

Measured memory_bytes: 89668
import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np
from functools import reduce

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.readline().split()
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.readline().split())
rf = lambda: map(float, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))
inf = float('inf')
mod = 10**9 + 7

x, y = rm()
if x%y == 0:
    print(-1)
else:
    print(x)














Measured memory_bytes: 27164
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e9;

ll N,A,B;
string S;

int main(){
    cin >> N >> A >> B;
    cin >> S;
    ll cnt1=0,cnt2=0;
    for(int i=0;i<N;i++){
        if(S[i] == 'a'){
            if(cnt1 < A+B){
                cnt1++;
                cout << "Yes" << endl;
            }else cout << "No" << endl;
        }else if(S[i] == 'b'){
            if(cnt2 < B && cnt1 < A+B){
                cnt1++;
                cnt2++;
                cout << "Yes" << endl;
            }else cout << "No" << endl;
        }else cout << "No" << endl;
    }
}

Measured memory_bytes: 896
#include<iostream>
#include <cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;


int main(){
  int H, W, K; cin >> H >> W >> K;
  ll dp[H+1][W] = {};
  dp[0][0] = 1; 
  rep(i, H){
    rep(j, W){
      rep(bits, 1<<(W-1)){
        bool OK=true;
        rep(l, W-2){
          if(((1<<l)&bits) && ((1<<l+1)&bits)) OK = false;
        }
        if(!(OK)) continue;
        if((bits & (1<<j)) && j+1<W) {dp[i+1][j+1]+=dp[i][j]; dp[i+1][j+1]%=mod;}
        else if((bits & (1<<(j-1))) && j>=1) {dp[i+1][j-1]+=dp[i][j]; dp[i+1][j-1]%=mod;}
        else {dp[i+1][j]+=dp[i][j]; dp[i+1][j]%=mod;}
      }
    }
  }
  cout << dp[H][K-1] << endl;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
#include <memory>
#include <regex>
using namespace std;

int main()
{
    int n;
    cin >> n;
    map<int, int> cnt;
    for(int i=0; i<n; ++i){
        int a;
        cin >> a;
        ++ cnt[a];
    }

    vector<int> v;
    for(const auto& p : cnt)
        v.push_back(p.second);
    sort(v.rbegin(), v.rend());
    int m = v.size();

    int i = 0;
    int x = 1;
    int y = n;
    int sum = n;
    for(int k=1; k<=n; ++k){
        while(y > 0 && x < k){
            -- y;
            if(y == 0){
                x = 0;
                break;
            }
            while(i < m && v[i] > y)
                ++ i;
            sum -= i;
            x = sum / y;
        }
        cout << y << endl;
    }

    return 0;
}


Measured memory_bytes: 15988
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using ll = long long;
using namespace std;
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
int gcd(int a, int b) { while (a) { b %= a; swap(a, b); } return b; }
bool is_swappable(int a, int b) { return gcd(a, b) == 1; }
int main() {
    // input
    int n; cin >> n;
    vector<int> a(n); repeat (i,n) cin >> a[i];
    // rearrange
    whole(sort, a);
    vector<int> b;
    vector<bool> used(n);
    function<void (int)> go = [&](int i) {
        used[i] = true;
        b.push_back(a[i]);
        repeat (j,n) if (not used[j] and not is_swappable(a[i], a[j])) {
            go(j);
        }
    };
    repeat (i,n) if (not used[i]) {
        go(i);
    }
    // insertion sort
    repeat (i,n) {
        int j = i;
        for (int k = i-1; k >= 0 and is_swappable(b[k], b[i]); -- k) {
            if (b[k] < b[i]) j = k;
        }
        rotate(b.begin() + j, b.begin() + i, b.begin() + i + 1);
    }
    // output
    for (auto it : b) cout << it << ' '; cout << endl;
    return 0;
}

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

#define nl "\n"
#define db(a) cout << (#a) << " = " << (a) << endl
#define ll long long
#define MOD 1000000007

int mod(int a, int b) {return a >= 0 ? a % b : (b + a % b) % b;}
int dceil(int a, int b) {return (a + b - 1) / b;}
/***********************************/

#define N -1

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	/*******************************/
	ll n, k;
	cin >> n >> k;
	vector<pair<ll, ll>> cps;
	for (int i = 0; i < n; i++) {
		ll a, b;
		cin >> a >> b;
		cps.push_back({a, b});
	}
	sort(cps.begin(), cps.end());
	for (int i = 0; i < n; i++) {
		if (cps[i].second >= k) {
			cout << cps[i].first << "\n";
			break;
		}
		k -= cps[i].second;
	}
	return 0;
}

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

using namespace std;

#define REPI(x) for(int i=0;i<x;i++)
#define REPJ(x) for(int j=0;j<x;j++)
#define SCANFD(x) scanf("%d",&x)

int main(){
  map<int, int> m;
  int X,N,b,e;

  cin >> X >> N;

  REPI(N)
  {
    cin >> b;
    m[b] = 1;
  }
  
  e = 0;
  
  while (e <= 100)
  {
    if (m[X - e] == 0)
    {
      cout << X - e << endl;
      break;
    }
    
    if (m[X + e] == 0)
    {
      cout << X + e << endl;
      break;
    }
    e++;
  }
  
  return 0;
}


Measured memory_bytes: 3584
/*
 * AOJ 2266: Cache Strategy
 * ?¢??????????n????????????????????????m????????????????????????????????????????????????????????§?????????????°????????????¨?????????????????\?????\???????????\??????????????????????????±?´???°?????°??????????????\?????¢????±?????°??????±?´????
 * ?±???????????°??´?
 * ??????????°??????\???????????????????????±???????????????????¬?????????¢???????????±?´??????°???????????????????????¨???????????????????????????????????´??????????????????????????´???????????¨???????????????????????±?´????????????\????????????????????¶????°??????°?????´???????????????????????????1??±?´??´?????????????????????¨?????????INF??±?´?0???????°???´??????????????\????±?????°??´???¨??????????????\??????????????§??????????????°??????????¢??????????????§??????????????????????????????????????´????????????\?±????????¢???????????????¨Dijkstra????????¨Bellman-Ford???
 */

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> pii;

const int INF = 0x3f3f3f3f;

int a[10010], w[10010];
int pre[10010];

struct Edge {
  Edge() {}

  Edge(int _v, int _cap, int _cost, int _rev) : v(_v), cap(_cap), cost(_cost), rev(_rev) {}

  int v, cap, cost, rev;
};

vector<Edge> e[10010];
int n;
int d[10010];
int pv[10010], pe[10010];

void AddEdge(int u, int v, int cap, int cost) {
  e[u].push_back(Edge(v, cap, cost, e[v].size()));
  e[v].push_back(Edge(u, 0, -cost, e[u].size() - 1));
}

int MinCostFlow(int s, int t, int f) {
  int ans = 0;
  while (f > 0) {
    memset(d, 0x3f, sizeof(d));
    d[s] = 0;
    bool update = true;
    while (update) {
      update = false;
      for (int i = 0; i < n; ++i) {
        if (d[i] == INF) continue;
        for (int j = 0; j < e[i].size(); ++j) {
          Edge &te = e[i][j];
          if (te.cap > 0 && d[te.v] > d[i] + te.cost) {
            d[te.v] = d[i] + te.cost;
            pv[te.v] = i;
            pe[te.v] = j;
            update = true;
          }
        }
      }
    }

    if (d[t] == INF) {
      return -1;
    }

    int cur = f;
    for (int i = t; i != s; i = pv[i]) {
      cur = min(cur, e[pv[i]][pe[i]].cap);
    }
    ans += cur * d[t];
    f -= cur;
    for (int i = t; i != s; i = pv[i]) {
      Edge &te = e[pv[i]][pe[i]];
      te.cap -= cur;
      e[i][te.rev].cap += cur;
    }
  }
  return ans;
}

int main() {
  int M, N, K, ans = 0;
  scanf("%d%d%d", &M, &N, &K);
  for (int i = 0; i < N; ++i) {
    scanf("%d", &w[i]);
  }
  for (int i = 0; i < K; ++i) {
    scanf("%d", &a[i]);
    --a[i];
  }
  K = unique(a, a + K) - a;

  memset(pre, -1, sizeof(pre));
  for (int i = 0; i < K; ++i) {
    ans += w[a[i]];
    if (pre[a[i]] != -1) {
      AddEdge(pre[a[i]], i - 1, 1, -w[a[i]]);
    }
    pre[a[i]] = i;
  }
  for (int i = 1; i < K; ++i) {
    AddEdge(i - 1, i, M - 1, 0);
  }
  n = K;
  ans += MinCostFlow(0, n - 1, M - 1);
  printf("%d\n", ans);

  return 0;
}

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

using namespace std;

const int N = 1e5 + 5;

int x[N], p[N], n, s;

int main() {
  scanf("%d %d", &n, &s);
  for (int i = 0; i < n; ++i) {
    scanf("%d %d", x+i, p+i);
  }
  if (s < x[0]) {
    printf("%lld\n", abs(x[n-1] - s));
    return 0;
  }
  if (x[n-1] < s) {
    printf("%lld\n", abs(x[0] - s));
    return 0;
  }
  int l = 0, r = n-1;
  bool left = p[l] < p[r];
  long long sudah = 0;
  long long ans = 0;
  int last = s;
  if (left) sudah += p[l], last = x[l], ++l;
  else sudah += p[r], last = x[r], --r;
  while (l < r && x[l] < s && x[r] > s) {
    bool pilih = left;
    if (left) {
      pilih = ((sudah + p[r]) > p[l]);
    }
    else {
      pilih = ((sudah + p[l]) < p[r]);
    }
    if (pilih) {
      ans += abs(x[l] - last);
      last = x[l];
      sudah += p[l];
      ++l;
    }
    else {
      ans += abs(x[r] - last);
      last = x[r];
      sudah += p[r];
      --r;
    }
    left = pilih;
  }
  if (x[l] > s) {
    ans += abs(x[r] - s);
    ans += abs(x[r] - last);
  }
  else {
    ans += abs(x[l] - s);
    ans += abs(x[l] - last);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1024
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("6");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2");
            //2
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("11");
            //5
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int X = int.Parse(InputList[0]);

        int SumVal = 0;
        for (int I = 1; I <= int.MaxValue; I++) {
            SumVal += I;
            if (Math.Abs(X) <= SumVal) {
                Console.WriteLine(I);
                break;
            }
        }
    }

    static int SolveNaive(int pX)
    {
        //到達可能な座標のSet
        var VisitedSet = new HashSet<int>();
        VisitedSet.Add(0);

        int I = 0;
        while (true) {
            if (VisitedSet.Contains(pX)) {
                return I;
            }
            I++;

            foreach (int EachInt in VisitedSet.ToArray()) {
                VisitedSet.Add(EachInt + I);
                VisitedSet.Add(EachInt - I);
            }
        }

    }
}


Measured memory_bytes: 13268
import javax.xml.crypto.Data;
import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {

        //??\???
        /*
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        */
        FastScanner sc = new FastScanner();
        String T  = sc.next();
        String P  = sc.next();
        for(int i = 0; i < T.length() - P.length() + 1; i++) {
            boolean sign = true;
            for(int j = 0; j < P.length(); j++) {
                if(T.charAt(i + j) != P.charAt(j)) {
                    sign = false;
                    break;
                }
            }
            if(sign) System.out.println(i);
        }

        //??????
    }

}

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() { return Double.parseDouble(next());}
}

Measured memory_bytes: 24356
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
int INF = 1e9+7;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
signed main() {
    int H,W;
    cin >> H >> W;
    vector<vector<int>>a(H,vector<int>(W));
    vector<vector<int>>ans(H*W,vector<int>(4));
    for(int i = 0; i < H; i++) {
        for(int j = 0; j < W; j++) {
            cin >> a[i][j];
        }
    }
    int X = 0;int Y = 0;int A = 0;int B = 0;
    int cnt = 0;
    while(X < H && Y < W) {
        bool ok = false;
        if(a[X][Y]%2 == 1) {
            ok = true;
            A = X; B = Y;
        }
        if(X%2 == 0) {
            if(Y+1 < W) {
                Y++;
            }
            else {
                X++;
            }
        }
        else {
            if(Y-1 >= 0) {
                Y--;
            }
            else {
                X++;
            }
        }
        if(ok && X < H) {
            a[X][Y]+=1;
            ans[cnt] = {A+1,B+1,X+1,Y+1};
            cnt++;
        }
    }
    cout << cnt << endl;
    for(int i = 0; i < cnt; i++) {
        for(int j = 0; j < 4; j++) {
            cout << ans[i][j];
            if(j+1 != 4) {
                cout << " ";
            }
        }
        cout << endl;
    }
}

Measured memory_bytes: 22760
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, s, e) for (int i = (int)(s); i < (int)(e); i++)
#define _rep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define _REP(i, e, s) for (int i = (int)(e - 1); i >= (int)(s); i--)

#define yes cout << "yes" << endl;
#define Yes cout << "Yes" << endl;
#define YES cout << "YES" << endl;

#define no cout << "no" << endl;
#define No cout << "No" << endl;
#define NO cout << "NO" << endl;

#define ll long long
#define ull unsigned long long
#define vi vector<int>

const double PI = 3.14159265358979323846;

ll gcd(ll a, ll b) {
    if (a < b) return gcd(b, a);
    ll r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

int main() {
    int N, M, sum = 0;
    vi v;
    cin >> N >> M;
    rep(i, M) {
        int n;
        cin >> n;
        sum += n;
    }
    if (N >= sum) {
        cout << N - sum << endl;
    } else {
        cout << -1 << endl;
    }
}


Measured memory_bytes: 3632
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():
    K, T = in_nn()
    a = in_nl()
    maxA = max(a)
    mT = -(-K // 2)
    ans = max(0, (maxA - mT) * 2 - 1)
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9196
package main

import (
	"bufio"
	"fmt"
	"io"
	"math"
	"os"
	"strconv"
	"strings"

)


func main() {
	solve(os.Stdin, os.Stdout)
}

type ReaderEx struct {
	baseScanner *bufio.Scanner
	words       []string
	nextWordIdx func() int
	initWordIdx func(int)
}

func NewScannerEx(stdin io.Reader) *ReaderEx {
	var this ReaderEx
	var idx int
	var wordsCnt int
	this.baseScanner = bufio.NewScanner(stdin)
	this.baseScanner.Buffer(make([]byte, 0), 1E+11)
	this.nextWordIdx = func() int {
		cur := idx
		idx = (idx + 1) % wordsCnt
		return cur
	}
	this.initWordIdx = func(wc int) {
		idx = 0
		wordsCnt = wc
	}
	return &this
}

func (me *ReaderEx) Scan(doSplit bool) (isScanned bool) {
	isScanned = me.baseScanner.Scan()
	if doSplit {
		me.words = strings.Fields(me.baseScanner.Text())
	} else {
		me.words = []string{me.baseScanner.Text()}
	}
	me.initWordIdx(len(me.words))
	return
}

func (me *ReaderEx) nextBytes() []byte {
	return []byte(me.words[me.nextWordIdx()])
}
func (me *ReaderEx) nextString() string {
	return me.words[me.nextWordIdx()]
}

type StringArray []string

func (me *ReaderEx) nextStringArray() StringArray {
	return me.words[me.nextWordIdx():]
}

func (me StringArray) toStrings() []string {
	return me
}

func (me StringArray) toInts() []int {
	strValues := me.toStrings()
	values := make([]int, len(strValues))
	for i, v := range strValues {
		n, err := strconv.Atoi(v)
		if err != nil {
			panic(err)
		}
		values[i] = n
	}
	return values
}
func (me *ReaderEx) nextInt() int {
	n, err := strconv.Atoi(me.words[me.nextWordIdx()])

	defer func() {
		if err != nil {
			panic(fmt.Sprintf("getInt(%d)", n))
		}
	}()
	return n
}

func pow(x, y, mod int) (ans int) {

	ans = 1
	for bit := 1 << uint(math.Floor(math.Log2(float64(y)))); ; bit >>= 1 {
		if y&bit != 0 {
			ans *= x
			if mod > 0 {
				ans %= mod
			}
		}
		if bit <= 1 {
			return
		}
		ans *= ans
		if mod > 0 {
			ans %= mod
		}
	}
}

type factType struct {
	prime int
	count int
}

func fact(n int) (facts []*factType) {

	for i := 2; i*i <= n; i++ {
		if n%i == 0 {
			fa := factType{prime: i}
			for n%fa.prime == 0 {
				n /= fa.prime
				fa.count++
			}
			facts = append(facts, &fa)
		}
	}
	if n > 1 {
		facts = append(facts, &factType{prime: n, count: 1})
	}
	return facts
}
func dec2bin(n int) (ret []bool) {
	for bit := 1 << uint(math.Floor(math.Log2(float64(n)))); ; bit >>= 1 {
		ret = append(ret, n&bit != 0)

		if bit <= 1 {
			return
		}
	}

}

func abs(v int) int {
	if v < 0 {
		v = -v
	}
	return v
}

func b2i(b bool) (i int) {
	if b {
		i = 1
	} else {
		i = 0
	}
	return
}

func solve(stdin io.Reader, stdout io.Writer) {

	r := NewScannerEx(stdin)
	r.Scan(true)
	c := r.nextString()

	fmt.Fprintln(stdout, string([]byte{c[0] + 1}))
}


Measured memory_bytes: 640
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static final int BIG_NUM  = 2000000000;
	public static final int MOD  = 1000000007;

	public static void main(String[] args) {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		char ch;


		try {

			String inputed = br.readLine();

			for(int i = 0; i < inputed.length(); i++){
				ch = inputed.charAt(i);

				if(ch >= 'a' && ch <= 'z'){
					System.out.printf("%c", ch-32);
				}else if(ch >= 'A' && ch <= 'Z'){
					System.out.printf("%c", ch+32);
				}else{
					System.out.printf("%c", ch);
				}
			}
			System.out.printf("\n");

		} catch (IOException e) {
			e.printStackTrace();
		}
	}
}


Measured memory_bytes: 28736
#include<iostream>
using namespace std;
int main(){
    int n,m,sum,count;
    int a[n];
    sum = 0;
    count = 0;
    cin >> n >> m;
    int m4 = m * 4;
    for (int i=0; i < n; i++){
        cin >> a[i];
        sum += a[i];
    }
    for(int j=0; j < n; j++){
        if(a[j] * m4 >= sum){
            count ++;
        }
    }
    if(count >= m ){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define FOR(i,a,b) for(long long i = (long long)(a); i < (long long)(b); i++)
#define RFOR(i,a,b) for(long long i = (long long)(a); i >= (long long)(b); i--)
#define MIN3(a,b,c) (a)<(b)?((a)<(c)?(a):(c)):((b)<(c)?(b):(c))
#define MAX(a,b) (a)>(b)?(a):(b)
#define MIN2(a,b) (a)<(b)?(a):(b)
using namespace std;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef long long ll;
#define ull unsigned long long
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll,ll> lll;
#define deb(x )     cerr << #x << " here "<< x << endl;
#define endl    "\n"
#define printCase() "Case #" << caseNum << ": "
inline bool is_palindrome(const string& s){ return std::equal(s.begin(), s.end(), s.rbegin()); }
const ll MOD = 1000000007;
const ll INF = 1e9+5;
const double eps = 1e-7;
const double PI = acos(-1.0);
#define coud(a,d) cout << fixed << showpoint << setprecision(d) << a;
inline void debug_vi(vi a) {FOR(i, 0, a.size()) cout<<a[i]<<" ";}
inline void debug_vll(vll a) {FOR(i, 0, a.size()) cout<<a[i]<<" ";}
#define ff first
#define ss second
/*----------------------------------------------------------------------*/

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

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int k,x;
    cin>>k>>x;
    int lo = max(-1000000, x - k + 1);
    int hi = min(1000000, x + k - 1);
    FOR(i, lo, hi+1) {
    	cout<<i<<" ";
    }

    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e15;

#include <math.h>
#define PI 3.14159265358979323846264338327950L
const int mxN = 1e9 + 7;
int n, m;
int cnt = 0;
vector<set<int>> a;
vector<int> p;
bool check(vector<set<int>> b) {
    for (int i = 0; i < m; i++) {
        if (b[i].size() % 2 != p[i]) return false;
    }
    return true;
}

vector<int> subset;
void search(int k) {
    if (k == n) {
        vector<set<int>> b = a;
        for (int i = 0; i < (int)subset.size(); i++) {
            for (int j = 0; j < m; j++) {
                b[j].erase(subset[i]);
            }
        }
        if (check(b)) cnt++;
    }
    else {
        search(k + 1);
        subset.push_back(k+1);
        search(k + 1);
        subset.pop_back();
    }
}


int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int k;
        cin >> k;
        set<int> s;
        for (int j = 0; j < k; j++) {
            int x;
            cin >> x;
            s.insert(x);
        }
        a.push_back(s);
    }
    
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        p.push_back(x);
    }
    search(0);
    

    
    cout << cnt;
    return 0;
}

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

int main (){
  int n;
  cin>>n;
  vector<int> v(n);
  rep(i,n){
    cin>>v.at(i);
  }
  int sum = 0;
  bool ok = true;
  rep(i,n){
    while(v.at(i) % 2 == 0){
      v.at(i)/=2;
      sum++;
    }
  }
  cout << sum << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define PI acos(-1)
#define X real()
#define Y imag()

typedef long long lli;
typedef complex<lli> P;
const lli MaX = 100005 , infi =1110111110111 , mod = 1000000007 ;
typedef pair<int,int> pii;
const int MX = 100005;

lli n , A[MX] , All , m;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>A[i];
        All+=A[i];
        m = max(m,A[i]);
    }
    if(m>=All-m)return cout<<"No",0;
    cout<<"Yes";
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#define N 100000

int A[N] = {0};

int serch(int x){
  if(x == A[x])
    return x;
  
  return A[x] = serch(A[x]);
}

int main(){
  int i, m, n, x, y, z;
  
  for(i=0; i<N; i++)
    A[i] = i;
  
  scanf("%d %d", &m, &n);
  
  for(i=0; i<n; i++){
    scanf("%d %d", &x, &y);
    if(serch(x) != serch(y))
      A[serch(y)] = serch(x);
  }
  
  scanf("%d", &z);
  
  for(i=0; i<z; i++){
    scanf("%d %d", &x, &y);
    if(serch(x) == serch(y))
      printf("yes\n");
    else
      printf("no\n");
  }
  
  return 0;
}

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

using namespace std;

const int MAX = 1 << 12;
const int INF = 1e9;

int dp[MAX];

int main() {
  int n, m; cin >> n >> m;
  
  for (int bits = 1; bits < MAX; ++bits) {
    dp[bits] = INF;
  }
  
  while (m--) {
    int a, b; cin >> a >> b;
    int c_bits = 0;
    while (b--) {
      int c; cin >> c;
      c_bits += 1 << (c-1);
      for (int bits = 0; bits < MAX; ++bits) {
        dp[bits|c_bits] = min(dp[bits|c_bits], dp[bits]+a);
      }
    }
  }
  
  cout << (dp[(1<<n)-1] == INF ? -1 : dp[(1<<n)-1]) << endl;
  return 0;
}

Measured memory_bytes: 256
def checker(list_,index):
  mid = sorted(list_[index:index+3])[1]
  if mid == list_[index+1]:
    return True
  return False

n = int(input())
ps = [int(i) for i in input().split()]
res = 0
for i in range(n-2):
  if checker(ps,i):
    res += 1
print(res)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
int main(){
  string a,b;
  int c;
  cin >> a >> b;
  c = stoi(a+b);
  for(int i=0;i*i<100100;i++){
    int r=i*i;
    if(r == c){
      cout << "Yes";
      return 0;
    }
  }
  cout << "No";
}


Measured memory_bytes: 256
import java.io.*;
import java.util.Arrays;  
  
public class Main{
  public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String strNyuryoku=br.readLine();
        
        //????§?????????§?????????
        String[] Syuturyoku=strNyuryoku.split(" ");
        
         //????????????????????????
         Arrays.sort(Syuturyoku);
        
        //????????????int?????????????????????????????\??????
        int iSyou=Integer.parseInt(Syuturyoku[0]);
        int iTyu=Integer.parseInt(Syuturyoku[1]);
        int iDai=Integer.parseInt(Syuturyoku[2]);
        
        //???????????\??£???????????°????????????
        System.out.println(iSyou +" "+ iTyu +" "+ iDai);
    }
}

Measured memory_bytes: 24224
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace AtCoderCS
{
    class Program
    {
        static void Main(string[] args)
        {
            List<string> yoko = new List<string>();
            List<string> tate = new List<string>();
            tate.Add("00000");
            for (int i = 0; i < 9; i++)
            {
                if (i % 2 == 0) yoko.Add("0" + Console.ReadLine().ToString() + "0");
                else tate.Add(Console.ReadLine().ToString());
            }
            tate.Add("00000");
            int x = 1;
            int y = 0;
            int[] vx = { 1, 0, -1, 0 };
            int[] vy = { 0, 1, 0, -1 };
            int muki = 0;

            StringBuilder ans = new StringBuilder();
            ans.Append('R');
            while (x != 0 || y != 0)
            {
                muki = (4+muki)%4;
                if (muki == 0)
                {
                    if (yoko[y + vy[muki]][x + vx[muki]] == '1')
                    {
                        y += vy[muki];
                        x += vx[muki];
                        ans.Append('R');
                        muki--;
                    }
                    else muki++;
                }
                else if (muki == 2)
                {
                    if (yoko[y + vy[muki]][x + vx[muki] + 1] == '1')
                    {
                        y += vy[muki];
                        x += vx[muki];
                        ans.Append('L');
                        muki--;
                    }
                    else muki++;
                }
                else if (muki == 1)
                {
                    if (tate[y + vy[muki]][x + vx[muki]] == '1')
                    {
                        y += vy[muki];
                        x += vx[muki];
                        ans.Append('D');
                        muki--;
                    }
                    else muki++;
                }
                else
                {
                    if (tate[y + vy[muki]+1][x + vx[muki]] == '1')
                    {
                        y += vy[muki];
                        x += vx[muki];
                        muki--;
                        ans.Append('U');
                    }
                    else muki++;
                }
            }
            Console.Out.WriteLine(ans.ToString());
        }
    }
}

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
typedef pair<int,int> pii;
typedef pair<long long, int> pli;

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

ll mod = 998244353;

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

  int a,b,c,k;
  cin >> a >> b >> c >> k;
  int ret = 0;
  ret += min(a,k);
  k -= min(a,k);
  if(k > 0){
    k -= min(k,b);
  }
  if(k > 0){
    ret -= min(c,k);
  }

  cout << ret << endl;
}

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

ans = 10**9+7

allN = 10**N #全ての整数の列
left = 9 ** N #左端が0か9
right = 9 ** N #右端が0か9
ryoutan = 8 ** N #両端0か9

ncc =  allN - left - right + ryoutan
print(int(ncc%ans))

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

int main(void) {
  int n;
  cin >> n;
  vector<long long> as(n);
  for (long long &a : as) cin >> a;
  vector<long long> bs(n + 1);
  vector<long long> cs(n + 1);
  bs[0] = 0;
  cs[n] = 0;
  for (int i = 0; i < n; ++i) {
    bs[i + 1] = bs[i] + as[i];
    cs[n - i - 1] = cs[n - i] + as[n - i - 1];
  }

  for (int i = 0; i <= n; ++i) {
    bs[i] = abs(bs[i] - cs[i]);
  }
  bs[0] = -1;
  bs[n] = -1;
  sort(bs.begin(), bs.end());

  cout << bs[2] << endl;
  return 0;
}

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

int main() {
  string s;
  cin >> s;
  cout << (s=="AAA"||s=="BBB"? "No":"Yes") << endl;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <iostream>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>

using namespace std;

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

static const double eps = 10e-8;

int main(){
	ll n;
	while(~scanf("%lld",&n)){
		if(n==0) break;
		int res=0;
		while(n!=1){
			if(n%2) n=n*3+1;
			else n/=2;
			res++;
		}

		printf("%d\n",res);
	}
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define forr(i, a, b) for(int i = (a); i < (int) (b); i++)
#define forn(i, n) forr(i, 0, n)
#define dforr(i, a, b) for(int i = (int)(b-1); i >= (a); i--)
#define dforn(i, n) dforr(i, 0, n)
#define db(v) cerr << #v << " = " << v << endl
#define pb push_back
#define sz(x) ((int)x.size())
#define fst first
#define snd second
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
const int MAXN = 405;

int di[] = {1, 0, -1, 0};
int dj[] = {0, 1, 0, -1};

int n, m;
string B[MAXN];
bitset<MAXN> pass[MAXN];

bool valid(int i, int j){
    if(i < 0 || n <= i)return false;
    if(j < 0 || m <= j)return false;
    return true;
}

ii bfs(ii st){
    int bk = 0, wt = 0;
    queue<ii> Q; Q.push(st);
    pass[st.fst][st.snd] = true;
    while(sz(Q)){
        ii p = Q.front(); Q.pop();
        int i = p.fst, j = p.snd;
//        printf("Tocamos %d-%d\n", i, j);
        if(B[i][j] == '#')bk++; else wt++;
        forn(k, 4){
            int ni = i + di[k], nj = j + dj[k];
            if(!valid(ni, nj))continue;
            if(pass[ni][nj]) continue;
            if(B[i][j] == B[ni][nj])continue;
            pass[ni][nj] = true;
            Q.push({ni, nj});
        }
    }
    return {bk, wt};
}

int main(){
//	freopen("input.txt", "r", stdin);
	ios :: sync_with_stdio(false);
	while(cin >> n >> m){
        forn(i, n)cin >> B[i];
        forn(i, n)pass[i] = 0;

        ll ans = 0;
        forn(i, n)forn(j, m)if(!pass[i][j]){
            ii cnt = bfs({i, j});
            ans += (ll)cnt.fst * cnt.snd;
//            db(ans);
//            printf("bk = %d, wt = %d\n", cnt.fst, cnt.snd);
        }
        cout << ans << endl;
	}
	return 0;
}


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

int prime(int);

int main(){
  int n,i,N,count=0;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&N);
    count+=prime(N);
  }
  printf("%d\n",count);
  return 0;
}
  
int prime(int x){
  int i=3;
  if(x==2){
    return 1;
  }
  if(x<2 || x%2==0){
    return 0;
  }
  while(i<=sqrt(x)){
    if(x%i==0) return 0;
      i=i+2;
  }
  return 1;
}

Measured memory_bytes: 596
#include  <iostream>
#include  <algorithm>
#include  <climits>
#include  <string>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define lrep(i, n, m) for(int i = n; i < m; i++)

typedef long long ll;
const int MAX = INT_MAX;

int main()
{	
	double r;
	cin >> r;
	cout << 2 * r * 3.14159 << endl;
}


Measured memory_bytes: 3784
#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<algorithm>

int main() {
	std::string leaf;
	std::cin >> leaf;
	if (leaf[0]==leaf[2]) {
		std::cout << "Yes" << std::endl;
	}
	else {
		std::cout << "No" << std::endl;
	}
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)

int main(){
  int r;
  cin >> r;
  if(r < 1200){
    cout << "ABC";
  }else if(r < 2800){
    cout << "ARC";
  }else{
    cout << "AGC";
  }
}


Measured memory_bytes: 768
import itertools
import math
import fractions
import functools
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
for i in range(n):
    a[i] -= 1
sum = b[a[0]]
for i in range(1,n):
    if a[i-1] + 1 == a[i]:
        sum += b[a[i]]+c[a[i]-1]
    else:
         sum += b[a[i]]

print(sum)

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

int main(){
    int N;
    cin >> N;
    vector<long long> A(N + 2, 0);
    vector<long long> sum(N + 2, 0);
    for(int i = 1; i <= N; i++)cin >> A[i];
    for(int i = 0; i < N + 1; i++){
        sum[i + 1] = sum[i] + abs(A[i + 1] - A[i]);
    }
    
    for(int i = 1; i <= N; i++){
        long long cost = sum[i - 1] + abs(A[i + 1] - A[i - 1]) + sum[N + 1] - sum[i + 1];
        cout << cost << endl;
    }
    return 0;
}

Measured memory_bytes: 2816
/*
时间:2020-7-28
书籍：算法和数据结构
内容：队列
页数：P65
*/
#include<iostream>
using namespace std;
int q;
class Task
{
public:
	string name="";
	int time=0;
	static int timecount;
	Task() = default;
	bool setWork()
	{
		if (time > ::q)
		{
			time -= ::q;
			timecount += q;
			return false;   //该项工作没有完成
		}
		else
		{
			timecount += time;
			cout << name << " " << timecount << endl;
			return true;
		}
	}
	Task& operator=(Task& task)
	{
		this->name = task.name;
		this->time = task.time;
		return *this;
	}
};
int Task::timecount = 0;
int main()
{
	int n;
	cin >> n >> ::q;
	int N = n + 1;
	Task* task = new Task[N];        //循环队列，多出一个储存单元用于判断队列是否满
	for (int i = 0; i < n; ++i)
	{
		cin >> task[i].name >> task[i].time;
	}
	int front = -1, rear = n - 1;
	bool judge = false;
	Task temp;
	while (rear != front)
	{
		front = (front + 1) % N;
		temp = task[front];
		judge = temp.setWork();
		if (!judge)
		{
			rear = (rear + 1) % N;
			task[rear] = temp;
		}
	}
	delete[]task;
	return 0;
}


Measured memory_bytes: 5996
#include <iostream>
#include <vector>
#include <string>
#include <set>
using namespace std;

int main() {
    string S;
    cin >> S;

    uint aval = static_cast<uint>('a');
    uint zval = static_cast<uint>('z');
    vector<int> counters(zval-aval+1, 0);

    for (size_t i=0; i<S.size(); ++i) {
        uint val = static_cast<uint>(S[i]) - aval;
        ++counters[val];
    }
    for (size_t i=0; i<counters.size(); ++i) {
        if (counters[i] == 0) {
            cout << static_cast<char>('a' + i) << endl;
            return 0;
        }
    }
    cout << "None" << endl;
}



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

using namespace std;

int main(void) {
    int Q;
    cin >> Q;

    while(Q--) {
        int64_t A, B;
        cin >> A >> B;
        int64_t s = (int64_t)sqrt(A*B);
        if(A == B) {
            cout << A+B-2 << endl;
        } else if(s*s == A*B) {
            cout << 2*s-3 << endl;
        } else if(s*(s+1) >= A*B) {
            cout << 2*s-2 << endl;
        } else {
            cout << 2*s-1 << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n, x, m;
    cin >> n >> x >> m;
    vector <bool> bl(m, 0);
    bl[x] = 1;
    vector <int> seq;
    seq.pb(x);
    ll vl = -1;
    while(1){
        x*=x;
        x%=m;
        if(!bl[x]){
            bl[x] = 1;
            seq.pb(x);
        }
        else{
            vl = x;
            break;
        }
    }
    ll ans = 0;
    while(seq[0] != vl && n > 0){
        ans+=seq[0];
        seq.erase(seq.begin());
        n--;
    }
    ll s = n/seq.size();
    ll sum = 0;
    ll md = n%(seq.size());
    for(auto a: seq) sum+=a;
    ans += sum*s;
    for(int i = 0; i < md; i++) ans+=seq[i];
    cout << ans << "\n";
}


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

using namespace std;


void solve() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        int x = floor(1.08 * (double)i);
        if (x == n) {
            cout << i; return;
        }
    }
    cout << ":(";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    cout << endl;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
#define mod 998244353
typedef long long ll;
ll dp[3005][3005];
ll pre[3005][3005];		
ll A[3005];
int main()
{
	int N,S;
	cin>>N>>S;
	for(int i = 1;i <= N; i++)
	cin>>A[i];
	for(int i = 1;i <= N; i++)
	{
		int a=A[i];
		pre[i][a]+=i;
		for(int j = 1; j <= S; j++)
		{
			dp[i][j]=(dp[i-1][j]+dp[i][j])%mod;
			pre[i][j]=(pre[i][j]+pre[i-1][j])%mod;
			if(j>=a)
			{
			pre[i][j]=(pre[i][j]+pre[i-1][j-a])%mod;
			}
			dp[i][j]=(dp[i][j]+pre[i][j])%mod;//*(N-i+1)
		}
	}
	cout<<dp[N][S]<<endl;
} 

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

int main() {
    int N;
    int count = 1;
    while (cin >> N, N) {
        cout << "Case " << count << ":" << endl;
        int dir = 1;
        vector<vector<int> > d(N, vector<int>(N));
        int x = 0, y = 0;
        for (int i = 0; i < N*N; i++) {
            d[x][y] = i+1;
            int nx = x - dir;
            int ny = y + dir;

            if (nx >= N) {
                nx = x;
                ny = y+1;
                dir *= -1;
            }

            if (ny >= N) {
                ny = y;
                nx = x+1;
                dir *= -1;
            }

            if (nx < 0) {
                if (ny >= N) nx++, ny--;
                else nx++;
                dir *= -1;
            }
            if (ny < 0) {
                if (nx >= N) ny++, nx--;
                else ny++;
                dir *= -1;
            }

            x = nx;
            y = ny;
        }

        for (auto i : d) {
            for (auto j : i) printf("%3d", j);
            cout << endl;
        }
        count++;
    }

    return 0;
}

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

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define all(x) (x).begin(),(x).end()
#define foreach(u,v) for(auto (u) : (v))
#define pb push_back
#define mp make_pair
#define mt make_tuple

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

const int inf = 1e9;
const ll linf = 1LL<<60;
const ll mod = 1e9 + 7;
const double eps = 1e-9;

/*
*/

int main()
{
  ll x, y;
  cin >> x >> y;

  if(abs(x-y) <= 1) cout << "Brown" << endl;
  else cout << "Alice" << endl;
  return 0;
}


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

using namespace std;

#define pb push_back
#define mp make_pair
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
typedef long long LL;
typedef pair<int, int> PII;

int n, x;
int a[2000], b[2000];

int main() {
    scanf("%d%d", &n, &x);
    forn(i, n) scanf("%d", a + i);
    forn(i, n) b[i] = a[i];
    LL ans = 0;
    forn(i, n) ans += a[i];
    for (int i = 1; i < n; ++i) {
        forn(j, n) {
            int pre = j - i;
            if (pre < 0) pre += n;
            b[j] = min(b[j], a[pre]);
        }
        LL cur = (LL)x * i;
        forn(j, n) cur += b[j];
        ans = min(ans, cur);
    }
    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 < (int)(n); i++)
typedef pair<int, int> P;

long long int n, d[200000], c[200000];

int main(){
  cin >> n;
  rep(i, n) d[i] = 0;
  long long int mx = 0;
  bool flag = false;
  rep(i, n){
    long long int tmp;
    cin >> tmp;
    d[tmp]++;
    mx = max(mx, tmp + 1);
    if(i == 0 && tmp == 0){
      flag = true;
    }
  }
  long long int sum;
  if(flag && d[0] == 1){
    sum = 1;
  }else{
    sum = 0;
  }
  rep(i, mx) cerr << d[i] <<" "; cerr << endl;
  for(int i = 1; i < mx; i++){
    long long int a = d[i - 1], b = d[i];
    long long int tmp = 1;
    rep(j, b){
      tmp *= a;
      tmp %= 998244353;
    }
    cerr << tmp << endl;
    sum *= tmp;
    sum %= 998244353;
  }
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 1024
# 参考文献:tonnnura172
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n = INT()

dic = defaultdict(int)
for i in range(1, n+1):
    dic["{},{}".format(str(i)[0], str(i)[-1])] += 1

# print(dic)

ans = 0
for n in dic.copy():
    s, e = n.split(",")
    # print(s, e)
    # if s == e:
    #     ans += dic[n] * dic[n]
    # else:
    ans += dic[n] * dic["{},{}".format(e, s)]
print(ans)        

exit()
c = [[0] * 10] * 10

# for i in range(1, n+1):
#     s_i = str(i)
#     print(s_i)
#     first = int(s_i[0])
#     last = int(s_i[-1])
#     print(first)
#     print(last)
#     c[first][last] += 1

# print(c)
# ans = 0
# for i in range(1, 10):
#     for j in range(1, 10):
#         ans += c[i][j] * c[j][i]
# print(ans)

Measured memory_bytes: 5144