akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define in(n, arr) for (int i = 0; i < n; ++i) cin >> arr[i]
#define out(n, arr) for (int i = 0; i < n; ++i) cout << arr[i] << " "
 
using namespace std;
int main()
{
	
	int n;
	cin >>  n;
	int** arr = new int*[n];
	for(int  i =0; i<n; i++)
		arr[i] = new int[3]();
	int** dp = new int*[n];
	for(int  i =0; i<n; i++)
		dp[i] = new int[3]();
	for(int  i =0; i<n; i++)
	{
		for(int  j =0; j<3; j++)
		{
			cin >> arr[i][j];
		}
	}
	dp[0][0] = arr[0][0];
	dp[0][1] = arr[0][1];
	dp[0][2] = arr[0][2];
	for(int  i =1; i<n; i++)
	{
		for(int  j =0; j<3; j++)
		{ 
		    if(j == 0)
		    	dp[i][j] = max(dp[i-1][1],dp[i-1][2]) + arr[i][j];
		    else if(j == 1)
		    	dp[i][j] = max(dp[i-1][0],dp[i-1][2]) + arr[i][j];
		    else
		    	dp[i][j] = max(dp[i-1][0],dp[i-1][1]) + arr[i][j];
		    
		}

	}
	cout << max(max(dp[n-1][0],dp[n-1][1]),dp[n-1][2]) << endl;
	



return 0;
}

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

using namespace std;

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> A(N);
  for (int i = 0; i < N; i++) cin >> A[i];
  sort(A.begin(), A.end());
  int answer = 0;
  for (int i = 0; i < K; i++) answer += A[i];
  cout << answer << endl;

  return 0;
}


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

using namespace std;

typedef long long int ll;
typedef string str;

typedef vector<str> vs;

//出力後改行を
#define fin(ans) cout << (ans) << endl;

//配列を昇順
template <typename T>
void Sort(T &n, ll a = 0, ll b = 0)
{
  if (b == 0)
  {
    return (sort(n.begin() + a, n.end()));
  }
  else
  {
    return (sort(n.begin() + a, n.begin() + b));
  }
}

//配列入力
template <typename T>
void V(T &n)
{
  for (ll i = 0; i < n.size(); i++)
  {
    cin >> n[i];
  }
}

//n ~ mの和
ll sigma(ll n, ll m)
{
  return ((n + m) * (m - n + 1) * 0.5);
}

void Main()
{
  ll n; cin >> n;
  vs s(n); V(s);
  map <str, ll> a;
  ll flag = 0;
  for(ll i = 0;i < n;i++)
  {
    Sort(s[i]);
    if(a.count(s[i])) a[s[i]]++;
    else a[s[i]] = 0;
  }
  for(ll i = 0;i < n;i++)
  {
    if(a.count(s[i]))
    {
      flag += sigma(1, a[s[i]]);
      a.erase(s[i]);
    }
  }
  fin(flag);
  return;
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(20);
  Main();
  return 0;
}


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


using namespace std;

void pluus(int* b,int n){
  b[n-2]++;
  for(int i=0;i<n-2;i++){
    if(b[n-2-i]==2){
      b[n-3-i]++;
      b[n-2-i]=0;
    }
  }
}
    
long long int keta(int *b,int j){
    int i=j;
    while(b[i]==0){
      i++;
    }
    return pow(10,i-j);
}



int main(){
  char a[11];
  cin >> a;
  int n=0;
  for(n;a[n]!='\0';n++){
  }
 if(n==1){
   cout << a[0]-0x30;
 }
 else{
  
  int b[n]={};
  b[n-1]=1;
  long long int sum = 0;
  for(int i=0;i<pow(2,n-1);i++){
    for(int j=0;j<n;j++){
      sum+=(a[j]-0x30)*keta(b,j);
      
    }
    pluus(b,n);
  }

  cout << sum;
  }
  return 0;
}





Measured memory_bytes: 256
#![allow(unused_imports)]
use std::cmp;
use std::collections::*;
use std::io::*;
use std::mem::swap;
#[allow(dead_code)]
struct Io<'a> {
    r: BufReader<StdinLock<'a>>,
    w: BufWriter<StdoutLock<'a>>,
    buf: VecDeque<String>,
    buf_str: String,
}
#[allow(dead_code)]
impl<'a> Io<'a> {
    fn r<T: std::str::FromStr>(&mut self) -> T {
        if self.buf.len() == 0 {
            self.r.read_line(&mut self.buf_str).unwrap();
            for w in self.buf_str.split_whitespace() {
                self.buf.push_back(w.to_owned());
            }
            self.buf_str.clear();
        }
        self.buf
            .pop_front()
            .unwrap()
            .parse()
            .unwrap_or_else(|_| panic!())
    }
    fn r_s(&mut self) -> String {
        if self.buf.len() == 0 {
            self.r.read_line(&mut self.buf_str).unwrap();
            for w in self.buf_str.split_whitespace() {
                self.buf.push_back(w.to_owned());
            }
            self.buf_str.clear();
        }
        self.buf.pop_front().unwrap()
    }
    fn w<T: std::fmt::Display>(&mut self, v: T) {
        write!(self.w, "{}", v).unwrap();
    }
    fn wl<T: std::fmt::Display>(&mut self, v: T) {
        writeln!(self.w, "{}", v).unwrap();
    }
    fn iter<'b, T: std::str::FromStr>(&'b mut self) -> IoIter<'a, 'b, T> {
        IoIter {
            io: self,
            p: std::marker::PhantomData,
        }
    }
}
#[allow(dead_code)]
struct IoIter<'a: 'b, 'b, T: std::str::FromStr> {
    io: &'b mut Io<'a>,
    p: std::marker::PhantomData<T>,
}
#[allow(dead_code)]
impl<'a, 'b, T: std::str::FromStr> Iterator for IoIter<'a, 'b, T> {
    type Item = T;
    fn next(&mut self) -> Option<T> {
        Some(self.io.r())
    }
}
fn main() {
    let stdin = stdin();
    let stdout = stdout();
    let r = BufReader::new(stdin.lock());
    let w = BufWriter::new(stdout.lock());
    let io = Io {
        r,
        w,
        buf: VecDeque::new(),
        buf_str: String::new(),
    };
    unsafe {
        problem(io);
    }
}

unsafe fn problem(mut io: Io) {
    let n: usize = io.r();
    let s: Vec<usize> = io.iter().take(n).collect();
    let q: usize = io.r();
    let t: Vec<usize> = io.iter().take(q).collect();

    let mut count = 0;
    'a: for ti in t {
        for si in &s {
            if ti == *si {
                count += 1;
                continue 'a;
            }
        }
    }
    io.wl(count);
}



Measured memory_bytes: 5052
#include<bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long a,b,k=0;
    cin>>a>>b;
    while(a>0){
        a=a-b;
        k++;
        if(a<=0)
         {cout<<k;
         break;}
    }
    return 0;
}
     
   




Measured memory_bytes: 3520
#include<stdio.h>
int main(){
	int a,b,c,d,k,n,i,x;
	scanf("%d%d",&n,&k);
	for(i=0;i<k;i++){
		scanf("%d%d",&a,&b);
		c=n-a+1;
		d=n-b+1;
		if(a>b)a=b;
		if(c>d)c=d;
		x=((a<c)?a:c)%3;
		if(!x)x=3;
		printf("%d\n",x);
	}
	return 0;
}


Measured memory_bytes: 2052
n = int(input())
x = list(map(int,input().split()))
y = list(map(int,input().split()))

z = 0
for i in range(len(x)):
    z += abs(x[i]-y[i])
print(z)

z = 0
for i in range(len(x)):
    z += (abs(x[i]-y[i]))**2
print(z**0.5)

z = 0
for i in range(len(x)):
    z += (abs(x[i]-y[i]))**3
print(z**(1/3))

z1 = 0
z2 = 0
for i in range(len(x)):
    z1 = abs(x[i]-y[i])
    if z1 > z2:
        z2 = z1
print(z2)


Measured memory_bytes: 5644
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i=0; i<(int)(n); i++)
#define ALL(x) x.begin(), x.end()
#define MOD 1000000007
typedef long long ll;

int main() {
    ll n, k;
    cin >> n >> k;
    vector<ll> vec;
    REP(i, n){
        ll num;
        cin >> num;
        vec.push_back(num);
    }
    sort(ALL(vec), std::greater<ll>());
    if(n <= k) cout << 0 << endl;
    else{
        ll sum;
        for(ll i=k; i<n; i++){
            sum += vec[i];
        }
        cout << sum << endl;
    }
    return 0;
}

Measured memory_bytes: 2420
#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
int L[1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>L[i];
	sort(L,L+N);
	int S=0;
	FOR(i,N-1) S+=L[i];
	if(S>L[N-1]) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 256
object Main {
  def main(args: Array[String]): Unit = {
    io.Source.stdin.getLines foreach (n => println(pi(n.toInt)))
  }
  val primes: IndexedSeq[Int] = prime_sieve(1000)
  val pi_cache: collection.mutable.Map[Int, Int] = collection.mutable.Map.empty
  val phi_cache: collection.mutable.Map[(Int, Int), Int] = collection.mutable.Map.empty

  def prime_sieve(n: Int): IndexedSeq[Int] = {
    val sieve = Array.fill(n)(true)
    for (i <- 3 to Math.sqrt(n).toInt by 2 if sieve(i))
      for (j <- i*i until sieve.length by 2*i) sieve(j) = false
    2 +: (for (i <- 3 until n by 2 if sieve(i)) yield i)
  }

  def bisect(n: Int): Int = {
    def loop(left: Int, right: Int): Int = {
      val mid = (left + right) / 2
      if (primes(mid) <= n && n < primes(mid+1)) mid+1
      else if (n < primes(mid)) loop(left, mid)
      else loop(mid+1, right)
    }
    if (n < primes.head) 0
    else if (n >= primes.last) primes.length
    else loop(0, primes.length)
  }
  def pi(x: Int): Int =
    pi_cache.getOrElseUpdate(x,
      if (x <= primes.last) bisect(x)
      else {
        val a = pi(Math.sqrt(Math.sqrt(x)).toInt)
        val b = pi(Math.sqrt(x).toInt)
        val c = pi(Math.cbrt(x).toInt)

        var result = phi(x, a) + ((b + a - 2) * (b - a + 1)) / 2
        for (i <- a + 1 to b) {
          val w = x / primes(i - 1)
          val b_i = pi(Math.sqrt(w).toInt)
          result -= pi(w)
          if (i <= c)
            for (j <- i to b_i)
              result = result - pi(w / primes(j - 1)) + j - 1
        }
        result
      }
    )
  def phi(x: Int, a:Int): Int =
    phi_cache.getOrElseUpdate(
      (x,a),
      {
        if (a == 1) (x + 1) / 2
        else phi(x, a - 1) - phi(x / primes(a - 1), a - 1)
      }
    )
}

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

typedef long long ll;
typedef pair<int, int> P;
const ll mod = 1e9 + 7, INF = 1e9, MAXN = 1e9;
int n, k; vector<vector<int>>sum;

int func(int i, int j) {
	return sum[i][j] - sum[i - k][j] - sum[i][j - k] + sum[i - k][j - k];
}

int main() {
	cin >> n >> k;
	int t = 2 * k, f = 4 * k;
	sum.resize(f + 5, vector<int>(f + 5, 0));
	for (int i = 0, x, y; i < n; i++) {
		char c; cin >> x >> y >> c;
		x %= t, y %= t;
		if (c == 'B')x += k;
		x %= t;
		sum[x][y]++; sum[x + t][y]++; sum[x][y + t]++; sum[x + t][y + t]++;
	}
	for (int i = 1; i < f; i++) {
		for (int j = 1; j < f; j++) {
			sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
		}
	}
	int ans = 0;
	for (int i = 0; i < t; i++) {
		for (int j = 0; j < t; j++) {
			int tmp = func(i + k, j + k) + func(i + t, j + t);
			ans = max(ans, tmp);
		}
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 63104
def main():
    N, T = map(int, input().split())
    c, t = zip(*(
        map(int, input().split())
        for _ in range(N)
    ))

    INF = float("inf")
    ans = INF
    for _c, _t in zip(c, t):
        if _t <= T:
            ans = min(ans, _c)

    if ans == INF:
        ans = "TLE"

    print(ans)


if __name__ == '__main__':
    main()


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

using namespace std;

typedef long long int ll;

#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;

int main()
{
	ll n;
	cin >> n;
	vector<ll> a(n);
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}

	ll ans = 0;
	for(int i = 0; i < n; i++){
		if(a[i] > 0){
			if(i>0 && a[i-1] == 1){
				ans += 1;
				a[i]--;
			}
			ans += a[i]/2;
			a[i] %= 2;
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for (long long i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
 
int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  cout << min(a,b) + min(c,d);
  
  return 0;
}

Measured memory_bytes: 3620
#ifndef CLASS_MODINT
#define CLASS_MODINT

#include <cstdint>

template<std::uint32_t mod>
class modint {
private:
	std::uint32_t n;
public:
	modint() : n(0) {};
	modint(std::int64_t n_) : n((n_ >= 0 ? n_ : mod - (-n_) % mod) % mod) {};
	std::uint32_t get() const { return n; }
	bool operator==(const modint& m) const { return n == m.n; }
	bool operator!=(const modint& m) const { return n != m.n; }
	modint& operator+=(const modint& m) { n += m.n; n = (n < mod ? n : n - mod); return *this; }
	modint& operator-=(const modint& m) { n += mod - m.n; n = (n < mod ? n : n - mod); return *this; }
	modint& operator*=(const modint& m) { n = std::uint64_t(n) * m.n % mod; return *this; }
	modint operator+(const modint& m) const { return modint(*this) += m; }
	modint operator-(const modint& m) const { return modint(*this) -= m; }
	modint operator*(const modint& m) const { return modint(*this) *= m; }
	modint pow(std::uint64_t b) const {
		modint ans = 1, m = modint(*this);
		while (b) {
			if (b & 1) ans *= m;
			m *= m;
			b >>= 1;
		}
		return ans;
	}
	modint inv() const { return (*this).pow(mod - 2); }
};

#endif // CLASS_MODINT

#include <vector>
#include <iostream>
using namespace std;
using modulo = modint<1000000007>;
int main() {
	int N, K;
	cin >> N >> K;
	vector<vector<modulo> > comb(N + 1);
	for (int i = 0; i <= N; ++i) {
		comb[i].resize(i + 1);
		comb[i][0] = 1;
		for (int j = 1; j <= i; ++j) {
			comb[i][j] = comb[i - 1][j - 1];
			if (j != i) comb[i][j] += comb[i - 1][j];
		}
	}
	int R = N - K;
	for (int i = 1; i <= K; ++i) {
		modulo mul = (i <= R + 1 ? comb[R + 1][i] : modulo(0));
		mul *= comb[K - 1][i - 1];
		cout << mul.get() << endl;
	}
	return 0;
}

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

class Program
{
	static void Main()
	{
		var t = Array.ConvertAll(Console.ReadLine().Split(new[] { ' ' }), number => int.Parse(number));

		var ans = 0;
		for (var i = 1; i <= t[0]; ++i) {
			var num = Cal(i);
			if (num >= t[1] && num <= t[2]) {
				ans += i;
			}
		}

		Console.WriteLine(ans);

		//デバッグ実行での確認用。そのまま提出しても問題なし
		Console.ReadKey();
	}

	static int Cal(int number)
	{
		var num = number / 10000;
		num += number % 10000 / 1000;
		num += number % 1000 / 100;
		num += number % 100 / 10;
		num += number % 10;

		return num;
	}
}


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

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

    int a, b;
    set<int> from_one;
    set<int> to_n;
    for (int i = 0; i < M; i++)
    {
        cin >> a >> b;
        if (a > b)
        {
            swap(a, b);
        }

        if (a == 1)
        {
            from_one.insert(b);
        }
        if (b == N)
        {
            to_n.insert(a);
        }
    }

    for (set<int>::iterator itr = from_one.begin(); itr != from_one.end(); itr++)
    {
        if (to_n.count(*itr) > 0)
        {
            cout << "POSSIBLE" << endl;
            return 0;
        }
    }
    cout << "IMPOSSIBLE" << endl;
}


Measured memory_bytes: 9600
#include <bits/stdc++.h>
#include <set>
#include <numeric>
#define rep(i,n) for (int i=0; i < (n); ++i)
#define all(a) a.begin(), a.end()
using ll = long long;
using namespace std;
 
// ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }


// const double PI = acos(-1);
// int gcd(int x, int y) { return (x % y)? gcd(y, x % y): y; }
// int a[12][12];
//平方根　= sqrt

int solve() {
  int r; cin >> r;

  if (r<1200) {
    cout << "ABC" << endl;
  }
  else if (r<2800) {
    cout << "ARC" << endl;
  }
  else {
    cout << "AGC" << endl;
 }
}


int main(){
  solve();
  return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(X: str, Y: str):
    if X < Y:
        print("<")
    elif X == Y:
        print("=")
    else:
        print(">")
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = next(tokens)  # type: str
    Y = next(tokens)  # type: str
    solve(X, Y)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
package main

import (
	"fmt"
)

var (
	h, w, d int
	a       = make(map[int][2]int)
	x       int
	q       int
	l, r    int
	lr      = make([][2]int, 0, q)
	mp      int
	cost    = make(map[int]int)
)

func main() {
	fmt.Scanln(&h, &w, &d)
	for i := 0; i < h; i++ {
		for j := 0; j < w; j++ {
			fmt.Scan(&x)
			a[x] = [2]int{i + 1, j + 1}
		}
	}

	fmt.Scan(&q)
	for i := 0; i < q; i++ {
		fmt.Scanln(&l, &r)
		lr = append(lr, [2]int{l, r})
	}

	cost[1] = 1
	for i := d + 1; i <= h*w; i++ {
		cost[i] = cost[i-d] +
			abs(a[i][0]-a[i-d][0]) + abs(a[i][1]-a[i-d][1])
	}

	for _, v := range lr {
		fmt.Println(
			cost[v[1]] - cost[v[0]],
		)
	}

}

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


Measured memory_bytes: 18048
n,w=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
sv=sum(list(zip(*l))[1])
dp=[10**12]*(sv+1)
dp[0]=0

for wi,vi in l:
    for j in range(sv-vi,-1,-1):
        dp[j+vi]=min(dp[j+vi],dp[j]+wi)
        #except IndexError:print(j,sv,vi);exit()
ans=0

for i in range(sv+1):
    if dp[i]<=w:ans=i
print(ans)

Measured memory_bytes: 41564
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
int main() {
  int n;
  cin >> n;
  vector<long double> a(n);
  rep(i,n) cin >> a[i];
  long double sum=0;
  rep(i,n){
    sum += 1/a[i];
  }
  cout << fixed << setprecision(10);
  cout << 1/sum << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
 
 
int main(){
 
    int n, m, x, y;
    int A[100][100] ,b[100], c;
 
    scanf( "%d %d", &n, &m );
     
 
    for( y=0; y<n; y++){
        for( x=0; x<m; x++ ){
            scanf( "%d", &A[x][y] ); 
        }
    }
    for( x=0; x<m; x++ ) scanf( "%d", &b[x] );
 
 
 
    for( y=0; y<n; y++){
        c = 0;
        for( x=0; x<m; x++ ){
            c += A[x][y]*b[x];
        }
        printf("%d\n", c);
    }
 
 
    return 0;
 
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <queue>
using namespace std;

int main(){
    string r ;
    cin >> r ;
    if (r == "ABC")
    {
        cout << "ARC" << endl ;
    }else
    {
        cout << "ABC" << endl ;
    }
    
    
}

Measured memory_bytes: 3620
#include <algorithm>
#include <iostream>
#include <string>

using namespace std;

int n;
string g[310];
char g2[310][310];

bool check(int a) {
    /*
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            g2[i][j] = g[(i + a) % n][j];
            */
    for (int i = 0; i < n; i++)
        for (int j = i; j < n; j++)
            /*
            if (g2[i][j] != g2[j][i])
                return false;
                */
            if (g[(i + a) % n][j] != g[(j + a) % n][i])
                return false;
    return true;
}

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

    int total = 0;
    for (int a = 0; a < n; a++)
        if (check(a))
            total++;
    total *= n;
    cout << total << endl;
}


Measured memory_bytes: 384
#include <algorithm>
#include <iostream>
#include <vector>

#include <stdlib.h>

using namespace std;

#define rep(i,a,b) for(int i=(int)(a); i<(int)(b); ++i)
#define SORT(x, n) sort(begin(x),begin(x)+n)

#define INF 2000000000000

int calc(int value){
	if(value - 500 >= 0){
		return value - 500;
	}
	else if(value - 100 >= 0){
		return value - 100;
	}
	else if(value - 50 >= 0){
		return value - 50;
	}
	else if(value - 10 >= 0){
		return value - 10;
	}
	else if(value - 5 >= 0){
		return value - 5;
	}
	else{
		return value - 1;
	}
}

int main()
{
	int price, oturi;
	while(true)
	{
		cin >> price;
		if(price == 0){ break; }
		oturi = 1000 - price;
		
		int count=0;
		while(true)
		{
			oturi = calc(oturi);
			//cout << oturi << endl;
			count++;
			if(oturi == 0){ break; }
		}
		
		cout << count << endl;
	}
	
	/*
	for(auto a : W){
		cout << a << endl;
	}
	*/
	
}

Measured memory_bytes: 1160
/*input
dreamerer
*/

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

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

	reverse(S.begin(), S.end());

	string a = "dream";
	string b = "dreamer";
	string c = "erase";
	string d = "eraser";

	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	reverse(c.begin(), c.end());
	reverse(d.begin(), d.end());

	int p = 0;
	bool flag = false;
	while(true){
		if(S.substr(p,5) == a){
			p+=5;
			continue;
		}
		if(S.substr(p,7) == b){
			p+=7;
			continue;
		}
		if(S.substr(p,5) == c){
			p+=5;
			continue;
		}
		if(S.substr(p,6) == d){
			p+=6;
			continue;
		}
		if(p == S.size()) flag=true;
		break;
	}

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


Measured memory_bytes: 512
n,k = map(int,raw_input().split(" "))
a = raw_input().split(" ")

dic = {}
for x in a:
  if x not in dic:
    dic[x] = 1
  else:
    dic[x] += 1
z = len(dic)
if z <= k:
  print 0
  exit()
ans = 0
d = sorted(dic.items(), key=lambda x: x[1])
for a in range(z-k):
  ans += int(d[a][1])
print ans

Measured memory_bytes: 49676
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
#define MAXN 100000
int lon[MAXN+5],jie=0;
int main(){
    int n,l;
    scanf("%d%d",&n,&l);
    for(int i=1;i<=n;i++)
        scanf("%d",&lon[i]);
    for(int i=1;i<n;i++)
        if(lon[i]+lon[i+1]>=l){
            jie=i;
            printf("Possible\n");
            break;
        }
    if(jie==0){
        printf("Impossible");
        return 0;
    }
    for(int i=1;i<jie;i++)
        printf("%d\n",i);
    for(int i=n-1;i>=jie+1;i--)
        printf("%d\n",i);
    printf("%d",jie);
    return 0;
}

Measured memory_bytes: 1152
//Can't Wait for Holiday
#include <bits/stdc++.h>
using namespace std;

int main(){
    map<string,int>day;
    day["MON"]=6;
    day["TUE"]=5;
    day["WED"]=4;
    day["THU"]=3;
    day["FRI"]=2;
    day["SAT"]=1;
    day["SUN"]=7;

    string s;
    cin>>s;
    cout<<day[s]<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cassert>
#include <set>
#include <map>
#include <cmath>
#include <numeric>
#include <iomanip>
#include <deque>
#include <tuple>

using namespace std;

typedef tuple<int, int, int, int, int, int, int, int> stup;

template <typename T1, typename T2>
bool cmin(T1 &a, const T2 &b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template <typename T1, typename T2>
bool cmax(T1 &a, const T2 &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

pair<double, pair<int, int>> ans;

double density(int water, int sugar) {
    if (!sugar)
        return 0;
    return (double)(100 * sugar) / (double)(sugar + water);
}

map<stup, bool> mem;
void solve(int cur_w, int cur_s, int a, int b, int c, int d, int e, int f) {
    if (mem[stup(cur_w, cur_s, a, b, c, d, e, f)])
        return;
    mem[stup(cur_w, cur_s, a, b, c, d, e, f)] = true;
    if (cur_s + cur_w > f || cur_s > cur_w / 100 * e)
        return;
    cmax(ans, make_pair(density(cur_w, cur_s), make_pair(cur_w, cur_s)));
    solve(cur_w + 100 * a, cur_s, a, b, c, d, e, f);
    solve(cur_w + 100 * b, cur_s, a, b, c, d, e, f);
    solve(cur_w, cur_s + c, a, b, c, d, e, f);
    solve(cur_w, cur_s + d, a, b, c, d, e, f);
}

signed main()
{
    int a, b, c, d, e, f;
    cin >> a >> b >> c >> d >> e >> f;
    solve(0, 0, a, b, c, d, e, f);
    
    cout << ans.second.first + ans.second.second << ' ' << ans.second.second;
}


Measured memory_bytes: 1408
#include<cstdio>
#include<vector>
#include<deque>
#include<utility>
#include<iostream>

using namespace std;


typedef unsigned int ui;
typedef vector<int> edge_t;


class vertex_t
{
	public:
	int m_is_passed;
	vector<int> m_edge;
};


int main(void)
{
	vector<vertex_t> vertex;
	deque<int> result;
	ui n, m, a, b, c=1;
	ui i, j;

	ios::sync_with_stdio(false);

	while(scanf("%u%u", &n, &m)==2)
	{
		result.clear();
		vertex.clear();
		vertex.resize(n+1);
		for(i=0;i<m;i++)
		{
			scanf("%u%u", &a, &b);
			vertex[a].m_edge.push_back(b);
			vertex[b].m_edge.push_back(a);
			c=a;
		}

		for(i=c;;)
		{
			edge_t& edge=vertex[i].m_edge;
			vertex[i].m_is_passed=1;
			result.push_front(i);
			for(j=0;j<edge.size();j++)
			{
				if(!vertex[edge[j]].m_is_passed)
				{
					i=edge[j];
					break;
				}
			}
			if(j>=edge.size()) break;
		}

		result.pop_back();
		for(i=c;;)
		{
			edge_t& edge=vertex[i].m_edge;
			vertex[i].m_is_passed=1;
			result.push_back(i);
			for(j=0;j<edge.size();j++)
			{
				if(!vertex[edge[j]].m_is_passed)
				{
					i=edge[j];
					break;
				}
			}
			if(j>=edge.size()) break;
		}

		printf("%u\n%d", result.size(), result[0]);
		for(i=1;i<result.size();i++)
		{
			printf(" %d", result[i]);
		}
		printf("\n");
	}

	return 0;
}


Measured memory_bytes: 7552
/*    Don’t Quit
    
    When things go wrong as they sometimes will;
        When the road you’re trudging seems all uphill;
            When the funds are low, and the debts are high;
                And you want to smile, but you have to sigh;
                    When care is pressing you down a bit
                        Rest if you must, but don’t you quit.
*/
#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(false);cin.tie(0)
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define all(a) a.begin(),a.end()
#define int long long
const int MOD=1e9+7;
const int N=3e5+10;
int a[N];
int32_t main()
{
    int n;
    cin>>n;
    cout<<(n/3)<<endl;




}

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

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

  using tsii = tuple<string, int, int>;
  using v = vector<tsii>;
  
  v p(N);
  for (int i = 0; i < N; i++) {
    string s;
    int score;
    cin >> s >> score;
    p.at(i) = make_tuple(s, -score, i + 1); // HINT 問題のソート順を考えるとスコアは逆転すると簡単
  }
  
  sort(p.begin(), p.end());
  
  for (auto e : p) {
    cout << get<2>(e) << endl;
  }
}


Measured memory_bytes: 3568
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < n; i++)
#define repr(i, n) for(ll i = n; i >= 0; i--)
#define reprr(i, m, n) for (ll i = m; i < n; i++)
#define inf 2e9
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
using Graph = vector<vector<pair<ll, ll>>>;


int main()
{
    ll N, M; cin >> N >> M;
    vll A(N);
    rep(i, N) {
        cin >> A[i];
    }
    vll sum(N);
    ll k = 0; 
    rep(i, N) {
        if (i == 0) sum[i] = A[i]; else sum[i] = A[i] + sum[i-1];
    }
    sum.insert(sum.begin(), 0);
    //for (auto elem : sum) cout << elem << " "; cout << endl;
    map<ll, ll> mp;
    rep(i, sum.size()) {
        mp[sum[i] % M]++;
    }

    ll cnt = 0;
    for (auto p : mp) {
        cnt += p.second * (p.second - 1) / 2;
    }
    //for (ll i = 0; i < N; i++) {
    //    for (ll j = i + 1; j < N + 1; j++) {
    //        if ((sum[j] - sum[i]) % M == 0) cout << i << " " << j << " " << sum[j] - sum[i] << endl;
    //    }
    //}
    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 5744
#include<bits/stdc++.h>          
using namespace std;
 
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define int long long
#define mk_p(a,b)	make_pair((a),(b))
using pii = pair<int,int>;
constexpr int INF  = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;

int gcd(int a,int b){return b ? gcd(b,a%b) : a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,d;
	cin >> n >> d;
	if(n < 4) cout << 0 << '\n';
	else{
		int cnt = 0;
		for(int i = n;i>3;--i){
			for(int j = 20;j <= d;j++){
					if(j %10 * (j /10) == i && j%10 >= 2){
						++cnt;
					}
			}
		}
		cout << cnt << '\n';
	}
	return 0;
}


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

using ll = long long;
static const ll MOD = 998244353;

// 繰り返し自乗法(x^nをmで割った余り) O(logn)
ll power(ll x, ll n, ll m) {
  ll res = 1;
  if (n > 0) {
    res = power(x, n / 2, m);
    if (n % 2 == 0) res = (res * res) % m;
    else res = (((res * res) % m) * x) % m;
  }
  return res;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int n;
  cin >> n;
  
  vector<int> a(n);
  int sum = 0;
  for (int i = 0; i < n; i++) {
    cin >> a.at(i);
    sum += a.at(i);
  }
  
  vector<vector<ll>> dp(n + 1, vector<ll>(90001));
  dp[0][0] = 1;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 90001; j++) {
      if (dp[i][j] == 0) continue;
      dp[i + 1][j] = (dp[i + 1][j] + dp[i][j] * 2) % MOD;
      dp[i + 1][j + a.at(i)] = (dp[i + 1][j + a.at(i)] + dp[i][j]) % MOD;
    }
  }
  
  ll ans = power(3, n, MOD);
  for (int j = (sum + 1) / 2; j <= 90000; j++) ans -= dp[n][j] * 3;
  ans = ((ans % MOD) + MOD) % MOD;
  
  if (sum % 2 == 0) {
    vector<vector<ll>> dp2(n + 1, vector<ll>(90001));
    dp2[0][0] = 1;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < 90001; j++) {
        if (dp2[i][j] == 0) continue;
        dp2[i + 1][j] = (dp2[i + 1][j] + dp2[i][j]) % MOD;
        dp2[i + 1][j + a.at(i)] = (dp2[i + 1][j + a.at(i)] + dp2[i][j]) % MOD;
      }
    }
    ans += dp2[n][sum / 2] * 3;
    ans %= MOD;
  }
  
  cout << ans << '\n';
}

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


int main() {
  int N, K;
  cin >> N >> K;
  int p[N];
  for (int i = 0; i < N; i++) {
    cin >> p[i];
  }
  int sum[N-K+1];
  sum[0] = 0;
  for (int i = 0; i < K; i++) {
    sum[0] += p[i];
  }
  
  priority_queue<int> que;
  que.push(sum[0]);
  
  for (int i = 0; i < N-K; i++) {
    sum[i+1] = sum[i] - p[i] + p[i+K];
    que.push(sum[i+1]);
  }
  
  int q = que.top();
  
  double ans = (K + q) / 2.0;
  cout << fixed << setprecision(10) << ans << endl;
}
  

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

int main(){
    int a,a2,a3,sum = 0;
    cin >> a;
    a2 = a*a;
    a3 = a*a*a;
    sum = a + a2 + a3;
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 3604
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
using namespace std;
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v;}
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str();}
typedef vector<int> vi;
typedef vector<vi>  vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EACH(t,i,c) for(t::iretator i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) FOR(i,0,n-1)
const double EPS = 1e-10;
const double PI = acos(-1.0);

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

int ddx[] = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
int ddy[] = {1, 1, 1, 0, 0, 0, -1, -1, -1};

struct state {
	int x, y, t;

public:
	state(int xx, int yy, int tt) {
		x = xx;
		y = yy;
		t = tt;
	}
};

int main() {
	int sx, sy;
	int n;
	int a, b;

	while(cin >> sx >> sy, !(sx==0 && sy==0)) {
		vvi field(14, vi(14, 0));
		queue<state> Q;

		Q.push(state(sx+2, sy+2, 0));
		cin >> n;
		
		REP(i, n) {
			cin >> a >> b;
			REP(j, 9) {
				field[a+2+ddx[j]][b+2+ddy[j]] += (1<<i);
			}
		}

		REP(i, 14) {
			field[0][i] = 0;
			field[1][i] = 0;
			field[i][0] = 0;
			field[i][1] = 0;
		}

		string msg = "NA";
		while(!Q.empty()) {
			state s = Q.front();
			Q.pop();
			if(s.t == n) {
				msg = "OK";
				break;
			}

			REP(d, 12) {
				if(field[s.x+dx[d]][s.y+dy[d]]&(1<<s.t)) {
					Q.push(state(s.x+dx[d], s.y+dy[d], s.t+1));
				}
			}
		}

		cout << msg << endl;
	}

	return 0;
}

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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// グラフの辺表現
using Edge = map<pair<int,int>,int>;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

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

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

// pairsをsecond優先キーとして昇順ソート
bool compare_by_b(pair<ll, ll> a, pair<ll, ll> b) {
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        return a.first < b.first;
    }
}

int main()
{
    cout << fixed << setprecision(15);
    ll N, M;
    cin >> N >> M;

    vector<pair<ll, ll> > pairs(M);

    REP(i, M){
        cin >> pairs[i].first >> pairs[i].second;
    }
    // 2つ目のキーで昇順ソート
    sort(pairs.begin(), pairs.end(), compare_by_b);

    ll ans = 0;
    ll cut = 0;
    REP(i, M){
        // cout << pairs[i].first << " " << pairs[i].second << endl;
        if(i==0){
            cut = pairs[i].second-1;
            ans++;
        }
        else{
            if(cut >= pairs[i].first) continue;
            else{
                cut = pairs[i].second-1;
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

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

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define REP(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) std::cout << x << '\n'
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define sz(x) ((int)(x).size())
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { ll g = gcd(a, b); return a / g * b; }
const int dx[4] = { 1, 0, -1,  0 };
const int dy[4] = { 0, 1,  0, -1 };
const int INF = INT_MAX / 2;
const ll  inf = LLONG_MAX / 2;
const int mod = 1000000007;
const int MAX_N = 101010;
const long double PI = acos(-1);

std::map<ll, ll> mp;

void prime_factor(ll n) {
	for (ll i = 2; i * i <= n; i++) {
		while (n % i == 0) {
			++mp[i];
			n /= i;
		}
	}
	if (n != 1) mp[n]++;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(10);
	/*------------------------------*/

	ll n;
	cin >> n;

	rep(i, n) {
		prime_factor(i + 1);
	}

	ll res = 1;
	for (auto m : mp) {
		res *= (m.second + 1);
		res %= mod;
	}

	out(res);

	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;

int check(string a, string b) {
	if (a.size() > b.size())return check(b, a);
	else if (a.size() == b.size()) {
		
		vector<int>anums(26), bnums(26);
		for (int i = 0; i < a.size(); ++i) {
			anums[a[i] - 'a']++;
		}
		for (int i = 0; i < b.size(); ++i) {
			bnums[b[i] - 'a']++;
		}
		if (anums == bnums) {
			for (int i = 0; i < a.size() - 1; ++i) {
				swap(a[i], a[i + 1]);
				if (a == b)return 1;
				swap(a[i], a[i + 1]);
			}
		}
		else {
			vector<int>amanys, bmanys;
			for (int i = 0; i < 26; ++i) {
				if (anums[i] > bnums[i]) {
					for (int j = 0; j < anums[i]-bnums[i]; ++j) {
						amanys.push_back(i);
					}
				}
				else if (anums[i] < bnums[i]) {
					for (int j = 0; j < bnums[i] - anums[i]; ++j) {
						bmanys.push_back(i);
					}
				}
			}
			if (amanys.size() > 2)return -1;
		}
	}
}
int main() {
	while (1) {
		int N, D; cin >> N >> D;
		if (!N)break;
		vector<string>names;
		for (int i = 0; i < N; ++i) {
			string name; cin >> name;
			names.push_back(name);
		}
		sort(names.begin(), names.end());
		vector<vector<string>>sas(N);
		for (int i = 0; i < N; ++i) {
			string aname(names[i]);
			for (int j = 0; j < aname.size(); ++j) {
				for (int k = 'a'; k <= 'z'; ++k) {
					string st(aname);
					if (k != st[j]) {
						st[j] = k;
						sas[i].push_back(st);
					}
				}
			}
			for (int j = 0; j < aname.size(); ++j) {
				string st(aname);
				st.erase(st.begin() + j);
				sas[i].push_back(st);
			}
			for (int j = 0; j <= aname.size(); ++j) {
				for (int k = 'a'; k <= 'z'; ++k) {
					string st(aname);
					st.insert(st.begin() + j, k);
					sas[i].push_back(st);
				}
			}
			for (int j = 0; j < aname.size()-1; ++j) {
				string st(aname);
				swap(st[j], st[j + 1]);
				sas[i].push_back(st);
			}
			sort(sas[i].begin(), sas[i].end());
		}
		vector<pair<int, int>>anss;
		for (int i = 0; i < N; ++i) {
			for (int j = i+1; j < N; ++j) {
				bool flag = false;
				for (int k = 0; k < sas[i].size(); ++k) {
					
					if (D==2&&binary_search(sas[j].begin(), sas[j].end(), sas[i][k])) {
						anss.push_back(make_pair(i, j));
						flag = true;
					}
					else if (sas[i][k] == names[j]) {
						anss.push_back(make_pair(i, j));
						flag = true;
					}
					if (flag)break;
				}
			}
		}
		for (int i = 0; i < anss.size(); ++i) {
			cout << names[anss[i].first] << ',' << names[anss[i].second] << endl;
		}
		cout << anss.size() << endl;
	}
	

	return 0;
}

Measured memory_bytes: 12256
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#define endl '\n'
#define fr(i,a,b) for(ll i=a; i<b; i++)
#define fr1(i,a,b) for(ll i=a; i>=b; i--)
#define ll long long int
#define ld long double
#define vi vector<ll>
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define mp(i,j) make_pair(i,j)
#define fi first
#define se second
#define input(a,n) fr(i,0,n)cin>>a[i]
#define output(a,n) fr(i,0,n)cout<<a[i]<<" "
#define dbg cout<<"hurr"<<endl;
#define dbg2 cout<<"hurr2"<<endl;
#define md 1000000007
#define sp << " " <<
#define pi 3.14159265358979323846
#define fixd(x) cout << fixed << setprecision(x);

int main()
{
    fast;
    ll n;
    cin >> n;
    ll a[n],dp[n];
    input(a,n);
    dp[0]=0;
    dp[1]=abs(a[0]-a[1]);
    fr(i,2,n)
        dp[i]=min(dp[i-2]+abs(a[i-2]-a[i]),dp[i-1]+abs(a[i-1]-a[i]));
    cout << dp[n-1];
}

Measured memory_bytes: 1792
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <limits.h>	
#define inf INT_MAX
#define INF 9223372036854775807
#define rep(i,n) for(i=0;i<n;i++)

int in(void){
	int i;scanf("%d",&i);
	return i;
}
long long llin(void){
	long long i;scanf("%lld",&i);
	return i;
}
void chin(char s[]){
	scanf("%s",s);
}
void print(int a){
	printf("%d\n",a);
}
void llprint(long long a){
	printf("%lld\n",a);
}
void print2(int a,int b){
	printf("%d %d\n",a,b);
}
long long max(long long a,long long b){
	return a>b?a:b;
}
long long min(long long a,long long b){
	return a<b?a:b;
}

int main(void){
	char s[27];
	int i,j;
	chin(s);
	rep(i,strlen(s)){
		rep(j,strlen(s)){
			if(i!=j&&s[i]==s[j]){
				puts("no");
				return 0;
			}
		}
	}
	puts("yes");
	return 0;
}

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

int main()
{
    int N;
    cin >> N;
    int cnt = 0;
    for(int i = 1; i <= N/2; i++)
    {
        int j = N - i;
        if(i != j) cnt++;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
ll dp[105][100005];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll w, n;
    cin >> n >> w;
    ll W[n+1] , v[n+1];
    for (int i = 1; i <= n; i++)
    {
        cin >> W[i] >> v[i];
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= w; j++)
        {
            if(W[i] <= j)dp[i][j] = max((v[i] + dp[i-1][j- W[i]]), dp[i-1][j]);
            else dp[i][j]= dp[i-1][j];
        }
    }
    cout << dp[n][w] << '\n';
}


Measured memory_bytes: 81596
#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 - 1; 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());

using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

ll mod = 1e9 + 7;

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

  string s;
  cin >> s;
  if(s.substr(0, 4) == "YAKI"){
    cout << "Yes" << endl;
    return 0;
  }
  cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main(){
    int m,h;
    string str;
    while(cin>>str){
        if(str=="-"){
            break;
        }
        cin>>m;
        for(int i=1;i<=m;i++){
            cin>>h;
            string a=str.substr(0,h);
            str.erase(0,h);
            str+=a;
        }
        cout<<str<<endl;
        
    }
    
    return 0;
}


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
using ll = long long;
#define vl vector<long long>
#define vvl vector<vector<long long>>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using pll = pair<long long,long long>;
#define cY cout<<"Yes"<<endl
#define cN cout<<"No"<<endl
const long long INF = 1LL << 60;
const long long MOD = 1000000007;

//最大最小の入れ替え
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

//約数列挙
vector<long long> divisor(long long n) {
    vector<long long> ret;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) ret.push_back(n / i);
        }
    }
    sort(ret.begin(), ret.end()); // 昇順に並べる
    return ret;
}
//コンビネーション
ll nCr(ll n, ll r) {
    ll ans = 1;
    for (int i = n; i > n - r; --i) {
        ans = ans*i;
    }
    for (int i = 1 ; i < r + 1; ++i) {
        ans = ans / i;
    }
    return ans;
}

//以下回答
int main(){
    ll N;
    cin>>N;
    vl vec(N);
    ll ans=0;
    rep(i,N) cin>>vec.at(i);
    ll a=0;
    bool down=false;
    if(N<3){
        ll ans=*max_element(all(vec));
        cout<<ans<<endl;
        return 0;
    }
    rep(i,N-1){
        if(vec.at(i)>vec.at(i+1)){
            down=true;
        }
        if(down&&vec.at(i)<vec.at(i+1)){
            ll max=*max_element(vec.begin()+a,vec.begin()+i+1);
            ans+=max;
            ans-=vec.at(i);
            down=false;
            a=i+1;
        }
        if(i==N-2){
            ll max=*max_element(vec.begin()+a,vec.end());
            ans+=max;
        }
    }
    cout<<ans<<endl;
}

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

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

    int max_cnt = 0;
    int ans = 1;
    for (int i = 1; i <= n; i++) {
        int cnt = 0;
        int num = i;
        while (num % 2 == 0) {
            cnt++;
            num /= 2;
        }
        if (cnt > max_cnt) {
            max_cnt = cnt;
            ans = i;
        }
    }

    cout << ans << endl;

    return 0;
}


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

using namespace std;

typedef long long  ll;

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

    int n;
    ll m;

    while (cin >> n >> m, n != 0 && m != 0) {
        ++n;
        vector<int> p(n);
        p[0] = 0;
        for (int i = 1; i < n; ++i)
            cin >> p[i];

        vector<int> dp(n * n);
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                dp[i * n + j] = p[i] + p[j];

        sort(dp.begin(), dp.end());
        dp.erase(unique(dp.begin(), dp.end()), dp.end());

        n = dp.size();
        ll ans = 0;
        for (int i = 0; i < n; ++i) {
            if (m < dp[i])
                break;
            ll tmp = *(upper_bound(dp.begin(), dp.end(), m - dp[i]) - 1);
            if (tmp + dp[i] <= m)
                ans = max(ans, tmp + dp[i]);
        }

        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 5408
/*Author - Shubham Gupta (@shubham107)*/
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vl;		typedef vector<int> vi;
typedef vector<vl> vvl;	  	typedef vector<vi> vvi;
typedef pair<ll, ll> pll;	typedef pair<int, int> pii;
#define forn(i,n) for(int i=0;i<n;i++)
#define rforn(i,n) for(int i=n-1;i>=0;i--)
#define forne(i,n) for(int i=1;i<=n;i++)
#define forse(i,s,e) for(int i=s;i<e;i++)
#define rforse(i,s,e) for(int i=e-1;i>=s;i--)
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define MOD 2019
#define F first
#define S second
#define pb push_back
#define fill(a,x) memset(a,x,sizeof a);
#define trav(a,x) for(auto &a:x)
#define INF	ll(1e18)
#ifdef SHUBHAM107
#include "../code-pieces/trace.h"
#else
#define trace(args...)
#endif

ll modpow(ll a, ll b, ll m = MOD) {
	a %= m; ll res = 1; while (b) {if (b & 1)res = res * a % m; a = a * a % m; b >>= 1;}
	return res;
}
ll bpow(ll a, ll b) {ll res = 1; while (b) {if (b & 1)res = res * a; a = a * a; b >>= 1;} return res;}
ll modinv(ll a) {return modpow(a, MOD - 2, MOD);}
void graph(vvi &adj, int m) {int x, y; forn(i, m) {cin >> x >> y; adj[x - 1].pb(y - 1); adj[y - 1].pb(x - 1);}}

const int mxN = 2e5 + 5;
ll nc2(int n){
	return (1LL*n*(n-1) )/ 2;
}
void solve() {
	string s;
	cin >> s;
	reverse(all(s));
	map<int, int> mp;
	int val = 0;
	mp[0]++;
	int fac = 1, value = 0;
	forn(i, sz(s)){
		value = (value + fac * (s[i] - '0')) % MOD;
		fac = (fac * 10) % MOD;
		mp[value]++;
	}
	ll ans = 0;
	trav(k, mp) ans += nc2(k.S);
	cout << ans;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
#ifdef SHUBHAM107
	freopen("inp.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("err.txt", "w", stderr);
#endif
	int t = 1;
	// cin >> t;
	while (t--) {
		solve();
	}
}


Measured memory_bytes: 3804
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
BC = [list(map(int, input().split())) for _ in range(M)]
BC.sort(key=lambda x:x[1],reverse=True)
i = 0
for bc in BC:
    for _ in range(bc[0]):
        if i > len(A)-1:
            break
        if A[i] > bc[1]:
            break
        A[i] = bc[1]
        i += 1
print(sum(A))

Measured memory_bytes: 81688
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++)
#define All(v) (v).begin(), (v).end()
#define pb push_back
#define MP(a, b) make_pair((a), (b))
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int INF = 1 << 30;
const ll LINF = 1LL << 60;
const int MOD = 1e9 + 7;

ll rec(int left, int right, vector<ll> &B, vector<vector<ll>> &dp) {
    if(left >= right)
        return 0;
    int l = left, r = right;
    if(dp[l][r] > 0)
        return dp[l][r];
    if(B[left] > B[right])
        left++;
    else
        right--;

    ll ret = max(rec(left + 1, right, B, dp) + B[left],
                 rec(left, right - 1, B, dp) + B[right]);
    return dp[l][r] = ret;
}

int main() {
    int N;
    cin >> N;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];
    ll res = 0;
    vector<ll> B(2 * N);
    rep(i, 2 * N) B[i] = A[i % N];
    vector<vector<ll>> dp(4100, vector<ll>(4100, -1));

    for(int i = 0; i < N; i++) {
        res = max(rec(i + 1, N + i - 1, B, dp) + A[i], res);
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 134600