akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef long long ll;

typedef pair<ll, ll> P;

int main() {
    ll N, C;
    cin >> N >> C;
    vector<P> p(N);
    rep(i, N) cin >> p[i].first >> p[i].second;

    vector<ll> clockwise_sum(N + 1); // 時計回りにi個まで取ったときのカロリー
    ll pos = 0;
    rep(i, N) {
        clockwise_sum[i + 1] = clockwise_sum[i] + p[i].second - (p[i].first - pos);
        pos = p[i].first;
    }

    vector<ll> counter_clockwise_sum(N + 1); // 反時計回りにi個まで取ったときのカロリー
    pos = C;
    rep(i, N) {
        counter_clockwise_sum[i + 1] = counter_clockwise_sum[i] + p[N - 1 - i].second - (pos - p[N - 1 - i].first);
        pos = p[N - 1 - i].first;
    }

    vector<ll> clockwise_max(N + 1); // clockwise_max[i]:時計回りにi個まで取って良いときのmax値
    rep(i, N) clockwise_max[i + 1] = max(clockwise_max[i], clockwise_sum[i + 1]);

    vector<ll> counter_clockwise_max(N + 1); // counter_clockwise_max[i]:反時計回りにi個まで取ってよいときのmax値
    rep(i, N) counter_clockwise_max[i + 1] = max(counter_clockwise_max[i], counter_clockwise_sum[i + 1]);

    ll ans = 0;

    // 時計回り
    rep(i, N) {
        chmax(ans, clockwise_sum[i + 1]); // 時計回りに取るだけの場合
        chmax(ans, clockwise_sum[i + 1] - p[i].first + counter_clockwise_max[N - 1 - i]);
    }

    // 反時計回り
    rep(i, N) {
        chmax(ans, counter_clockwise_sum[i + 1]); // 反時計回りに取るだけの場合
        chmax(ans, counter_clockwise_sum[i + 1] - (C - p[N - 1 - i].first) + clockwise_max[N - 1 - i]);
    }

    cout << ans << endl;
}


Measured memory_bytes: 4992
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <vector>
#include <cmath>
#include <random>
#include <climits>
#include <set>
#include <deque>

#define mod 1000000007
#define REP(i,n) for(int (i)=0; (i)<(n); (i)++)

using namespace std;
using ll = long long;

int X[] = {-1, 0, 1, 1, 1, 0, -1, -1};
int Y[] = {1, 1, 1, 0, -1, -1, -1, 0};

int gcd(int a, int b) {
    int x = max(a, b);
    int y = min(a, b);
    int z = x % y;
    if(z == 0){
        return y;
    }else{
        return gcd(y, z);
    }
}

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

void solve() {
    int n, x, sum=0;
    vector<int> s;
    cin >> n;
    REP(i, n) cin >> x, s.push_back(x), sum+=x; 

    sort(s.begin(), s.end());

    for(auto i = s.begin(); i != s.end(); i++){
        if(sum%10 != 0){
            cout << sum << endl;
            return;
        }
        if(*i%10 != 0){
            sum -= *i;
        }
    }
    cout << 0 << endl;
}

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

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

signed main()
{
    string s,t; cin>>s>>t;

    int N=s.size();
    REP(i,N){
        if(s==t){
            cout<<"Yes"<<endl;
            return 0;
        }
        s=s.back()+s.substr(0,N-1);
    }
    cout<<"No"<<endl;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math

n = getN()
nums = getList()

# nums.sort(reverse=True)
mx = max(nums)
mn = (mx+1) // 2
mndx = (mx % 2) + 1

from collections import Counter

cnt = Counter(nums)

for i in range(mn+1, mx+1):
    if cnt[i] < 2:
        print("Impossible")
        sys.exit()

if cnt[mn] != mndx:
    print("Impossible")
else:
    print("Possible")

Measured memory_bytes: 38384
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#define mod 1000000007
using namespace std;
int n,a[100010],f[100010],m,ans=1,tot,head[100010];
struct rd{int next,to;}road[200010];
inline void addedge(int x,int y)
{
  road[++tot].next=head[x];
  road[tot].to=y;
  head[x]=tot;
}
inline int dfs(int x,int fa,int p,int p2)
{
  ans=1ll*ans*(m-p-p2)%mod;
  int t1=1;
  for(int now=head[x];now;now=road[now].next)
    if(road[now].to!=fa) dfs(road[now].to,x,t1,fa!=0),t1++;
  return t1;
}
int main()
{
  cin>>n>>m;
  for(int i=1,x,y;i<n;i++)
  {
    scanf("%d%d",&x,&y);
    addedge(x,y);
    addedge(y,x);
  }
  dfs(1,0,0,0);
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3712
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<list>
#include<cstdint>
#include<bits/stdc++.h>
#include<queue>
#include<set>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep_r(i, n) for(int i = n-1; i >= 0; i--)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i++)
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((ll)(x).size())
#define bit(n) (1LL<<(n))
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define INF bit(60)
#define pb push_back
#define mod 1000000007

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

using namespace std;
using uif=uint_fast64_t;
using ll=long long int;

int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mod;a=1ll*a*a%mod;}while(b>>=1);return ans;}
int qp(int a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}

int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};


#define FACSIZE 2002

ll invfac[FACSIZE];
ll fac[FACSIZE];

ll mod_pow(ll ,ll );
ll mod_add(ll ,ll );
ll mod_mul(ll ,ll );
ll mod_div(ll ,ll );
void make_fact(ll );
void make_invfact(ll );



int main(void){

  string s,t;
  cin>>s;
  cin>>t;
  
  int ans=0;
  
  for(int i=0;i<s.size();i++){
  	if(s[i]==t[i]) ans++;
  }
	
  cout << ans << endl;
  
  return 0;

}

ll mod_pow(ll x,ll r){
  if(r==0) return 1;
  else if(r==1) return x%mod;
  else if(r%2==0){
    ll t=mod_pow(x,r/2)%mod;
    return t*t %mod;
  } 
  else{
    ll t=mod_pow(x,r/2)%mod;
    ll k= t*t %mod;
    return k*x%mod;
  } 
}
ll mod_add(ll a,ll b){
  return (a+b)%mod;
}

ll mod_mul(ll a,ll b){
  return (a*b)%mod;
}

ll mod_div(ll a,ll b){
  return mod_mul(a,mod_pow(b,mod-2));
}

void make_fact(ll n){
  fac[0]=1;
  rep(i,n){
    fac[i+1]=mod_mul(fac[i],i+1);
  }  
}

void make_invfact(ll n){
  invfac[n]= mod_pow( fac[n] ,mod-2);
  for(int i=n-1;i>=0;i--){
    invfac[i]=mod_mul(invfac[i+1],i+1);
  }

}

Measured memory_bytes: 256
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;
#define REP(i, j) for(int i = 0; i < (int)(j); ++i)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
typedef complex<double> P;

int a, b, c;

void solve(){
  FOR(p, 1, 10001){
    if(a % p) continue;
    int r = a / p;
    FOR(q, -10001, 10001){
      int s;
      if(q == 0) s = b / p;
      else s = c / q;
      if(p < r || (r == p && q < s)) continue;
      if(p * r == a && p * s + r * q == b && q * s == c){
        cout <<p <<" " <<q <<" " <<r <<" " <<s <<endl;
        return ;
      }
    }
  }
  cout <<"Impossible" <<endl;
}

int main() {
  while(cin >>a >>b >>c && a) solve();
  return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
    using namespace std;
    #define mod 1000000000000000000
    #define MOD 		1000000007
    #define ll long long
    #define mp 		make_pair
    #define pb 		push_back
    #define forn(i,n) 	for(ll i=0;i<n;i++)
    #define for1(i,n) 	for(ll i=1;i<=n;i++)
    #define forn1(i,n) 	for(int i=1;i<n;i++)
    #define rep(i,x,n)  for(ll i=x;i<=n;i++)
    #define repr(i,x,j) for(ll i=x;i>=j;i--)
    #define vi vector<ll>
    #define mii map<int,int>
    #define vii vector<pair<int,int>>
    #define vvi vector<vector<int>>
    #define pii pair<int,int>
    #define F first
    #define S second
    #define fill(a,x) memset(a,x,sizeof a);
    #define all(x) x.begin(),x.end()
    #define test ll t;cin>>t;while(t--)
    #define yes cout<<"YES"<<endl
    #define no cout<<"NO"<<endl
    #define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define R return 0
    int main()
    {
    	IOS;
        ll t,n,x,y,cnt=0;
        cin>>t>>n;
        while(t--)
        {
            cin>>x>>y;
            double l=sqrt(x*x+y*y);
            if(l<=n)
            cnt++;
        }
        cout<<cnt<<endl;
        R;
    }

Measured memory_bytes: 3696
"use strict";

var main = function main(input) {
  var N = parseInt(input.split(" ")[0]);
  var A = parseInt(input.split(" ")[1]);
  var B = parseInt(input.split(" ")[2]);
  var count = 0;

  for (var i = 1; i <= N; i++) {
    var sum = 0;
    var arr = i.toString().split("");
    var num = arr.length;

    for (var j = 0; j < num; j++) {
      sum += parseInt(arr[j], 10);
    }

    if (sum <= B && sum >= A) {
      count += i;
    }
  }

  console.log(count);
};

main(require('fs').readFileSync('/dev/stdin', 'utf8'));

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

int main(){

    long long n,k;
    cin>>n>>k;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin>>a[i];
    
    int t=1;
    vector<int> save;
    save.push_back(t-1);
    set<int> check;
    check.insert(t-1);

    int l,r,size;
    vector<int> loop;

    long long ans;

    while(1){
        t=a[t-1];
        if(!check.count(t-1)){
            check.insert(t-1);
            save.push_back(t-1);
        }
        else{
            r=check.size()-1;
            for(int i=0;i<check.size();i++){
                if(save[i]==t-1){
                    l=i;
                }
            }
            size=r-l+1;
            break;
        }
    }

    for(int i=0;i<size;i++){
        loop.push_back(save[l+i]);
    }

    if(k+1<=check.size()) cout<<save[k]+1<<endl;
    else{
        ans=(k+1-l)%size-1;
        if(ans==-1) ans+=size;
        cout<<loop[ans]+1<<endl;
    }





    return 0;
}

Measured memory_bytes: 15012
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define dump(x) cout << #x << " = " << (x) << endl;
using namespace std;
using ll = long long;
using P = pair<ll, ll>;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int r, D, x;
  cin >> r >> D >> x;
  int tmp = 0;
  for(int i = 0; i < 10; i++) {
    tmp = r * x - D;
    cout << tmp << endl;
    x = tmp;
  }

  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int l,r;
	scanf("%d%d",&l,&r);
	int k=l%2019,t=r%2019;
	if(r-l>=2*2019){
		puts("0");
		return 0;
	}
	int ans=2018;
	for(long long i=l;i<=r;i++){
		for(long long j=i+1;j<=r;j++){
			int num=(i*j)%2019;
			ans=min(ans,num);
		}
	}
	printf("%d\n",ans);
	return 0;
}

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

int main(void) {

    int d;
    while(cin >> d){
        int n = 600 / d;
        int ans = 0;
        for(int i=0; i<n; i++) ans += (i*d)*(i*d) * d;

        cout << ans << endl;
    }



    return 0;
}

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

int main(){
  int n,x;
  cin>>n;
  for(int i=3;i<=n;i++){
    if(i%3==0) cout<<" "<<i;
    else {
      x=i;
      while(x!=0){
	if(x%10==3){
	  cout<<" "<<i;
	  break;
	}

	x=x/10;
      }
    }
  }
  cout<<endl;

  return 0;
}



Measured memory_bytes: 3084
a,b=map(int,input().split())
s=input()
num=[str(i) for i in range(10)]
for i in range(a):
    if not(s[i] in num):
        print("No")
        exit()
if s[a]!="-":
    print("No")
    exit()
for i in range(a+1,a+b+1):
    if not(s[i] in num):
        print("No")
        exit()
print("Yes")

Measured memory_bytes: 3064
def nCr(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
size = 10**5 # size >= n
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, size + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

S = int(input())
ans = 0

for i in range(1, S//3 + 1):
    ans += nCr(S - 2 * i - 1, i - 1, mod)
    ans %= mod

print(ans)

Measured memory_bytes: 20800
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

// I/O
type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []rune {
	return []rune(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func (s *Scanner) nextFloatSlice(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextFloat()
	}
	return res
}

// Arithmetic
func max(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m < i {
			m = i
		}
	}
	return m
}

func min(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m > i {
			m = i
		}
	}
	return m
}

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

func pow(x, y int) int {
	res := 1
	for i := 0; i < y; i++ {
		res *= x
	}
	return res
}

func ceil(a, b int) int {
	if a%b == 0 {
		return a / b
	} else {
		return a/b + 1
	}
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

func lcm(a, b int) int {
	return a / gcd(a, b) * b
}

// Sort
type RuneSlice []rune

func (a RuneSlice) Len() int           { return len(a) }
func (a RuneSlice) Less(i, j int) bool { return a[i] < a[j] }
func (a RuneSlice) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

// Main
const MOD = int(1e+9) + 7
const INF = 1 << 60

type Work struct {
	a, b int
}

type ByB []Work

func (a ByB) Len() int           { return len(a) }
func (a ByB) Less(i, j int) bool { return a[i].b < a[j].b }
func (a ByB) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

func main() {
	sc := NewScanner()
	wtr := bufio.NewWriter(os.Stdout)
	defer wtr.Flush()
	N := sc.nextInt()
	W := make([]Work, N)
	for i := 0; i < N; i++ {
		W[i] = Work{sc.nextInt(), sc.nextInt()}
	}
	sort.Sort(ByB(W))
	cur := 0
	ok := true
	for i := 0; i < N; i++ {
		w := W[i]
		if cur+w.a <= w.b {
			cur += w.a
		} else {
			ok = false
			break
		}
	}

	if ok {
		fmt.Fprintln(wtr, "Yes")
	} else {
		fmt.Fprintln(wtr, "No")
	}
}


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

int main()
{
  	int req[3]={-1, -1, -1};
	int n,m;
    std::cin >> n >> m;
    for(int i=0;i<m;i++){
    	int pos, val;
        std::cin >> pos >> val;
        if(req[n-pos]==-1){
          	req[n-pos]=val;
        }else if(req[n-pos]!=val){
        	std::cout << "-1\n";
            return 0;
        }
    }
  	if(n==1){
      	if(req[0]==-1) req[0]=0;
    }else{
    for(int i=0;i<(n-1);i++){
        if(req[i]==-1){
			req[i]=0;
        }
    }
  	if(req[n-1]==-1){
		req[n-1]=1;
	}else if(n!=1 && req[n-1]==0){
        std::cout << "-1\n";
    	return 0;
    }
    }
    for(int i=0;i<n;i++){
    	std::cout << req[n-i-1];
    }
  	std::cout << "\n";
  	return 0;
}

Measured memory_bytes: 3136
def main():
    import sys
    input = sys.stdin.readline
    H, W = [int(x) for x in input().strip().split()]
    M = [0] * (H+2)
    M[0] = ['x'] * (W+2)
    M[-1] = ['x'] * (W+2)
    for h in range(H):
        M[h+1] = ['x'] + list(input().strip()) + ['x']

    dhdw = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    ans = 0
    for i in range(1, H+1):
        for j in range(1, W+1):
            if M[i][j] == 'x':
                continue
            cnt = {'.':0, '#':0}
            q = [(i, j, M[i][j])]
            cnt[M[i][j]] = 1
            M[i][j] = 'x'
            while q:
                h, w, m = q.pop()
                # print(h, w)
                # for h_ in range(H+2):
                #     print(M[h_])
                for dh, dw in dhdw:
                    if M[h+dh][w+dw] != 'x' and m != M[h+dh][w+dw]:
                        cnt[M[h+dh][w+dw]] += 1
                        q.append((h+dh, w+dw, M[h+dh][w+dw]))
                        M[h+dh][w+dw] = 'x'
            # for h_ in range(H+2):
            #     print(M[h_])
            # print(cnt['.']*cnt['#'])
            ans += cnt['.']*cnt['#']
    
    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 17772
#include<stdio.h>

int IsPrime(int n) {
    for(int i = 2; i*i <= n; i++) {
        if(n % i == 0) {
            return 0;
        }
    }
    return 1;
}

int main(void){

int n,count = 0;
long long p;

scanf("%d",&n);
 for(int i = 0; i < n; i++) {
     scanf("%lld",&p);

       if(IsPrime(p)){
       count++;
       }
   }
printf("%d\n",count);
return 0;
   }


Measured memory_bytes: 2108
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#define ll long long
#define rg register
struct ios{
	template<typename TP>
	inline ios operator >> (TP &x)
	{
		TP f=1;x=0;rg char c=getchar();
		for(;c>'9' || c<'0';c=getchar()) if(c=='-') f=-1;
		for(;c>='0' && c<='9';c=getchar()) x=(x<<3)+(x<<1)+(c^'0');
		x*=f;
		return *this;
	}
	template<typename TP>
	inline ios operator << (TP x)
	{
		int top=0,s[66];
		if(x<0) x=-x,putchar('-');
		if(!x) putchar ('0');
		while(x) s[++top]=x%10+'0',x/=10;
		while(top) putchar(s[top--]);
		return *this;
	}
	inline ios operator << (char s)
	{
		putchar(s);
		return *this;
	}
}io;
const int p=998244353;
const int N=3e5+5;
int n,A,B,fac[N],inv[N];
ll k;
inline int pow(int a,int b)
{
	int ans=1;
	for(;b;b>>=1)
	{
		if(b&1) ans=(ll)ans*a%p;
		a=(ll)a*a%p;
	}
	return ans%p;
}
inline int C(int n,int m) {return (ll)fac[n]*inv[m]%p*inv[n-m]%p;}
int ans;
int main()
{
	io>>n>>A>>B>>k,inv[0]=fac[0]=1;
	if(!k) {io<<1;return 0;}
	for(rg int i=1;i<=n;++i) fac[i]=(ll)fac[i-1]*i%p;
	inv[n]=pow(fac[n],p-2);
	for(rg int i=n-1;i>=1;--i) inv[i]=(ll)inv[i+1]*(i+1)%p;
	for(rg int i=0;i<=n;++i)
	{
		ll tmp=k-(ll)i*A;
		if(tmp<0) break;
		if(tmp%B==0 && tmp<=(ll)B*n)
			ans=(ans+(ll)C(n,i)*C(n,tmp/B)%p)%p;
	}
	io<<ans;
	return 0;
}


Measured memory_bytes: 2560
#include <iostream>
#include <vector>
#include <cstdlib>
#include <limits>

using namespace std;

template<class T> inline bool change_min(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

const long long INF = numeric_limits<long long>::max();

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

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

    long long dp[N + K];
    for (int i = 0; i < N + K; i++) {
        dp[i] = INF;
    }

    dp[0] = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 1; j <= K; j++) {
            change_min(dp[i + j], dp[i] + abs(h[i] - h[i + j]));
        }
    }

    cout << dp[N - 1] << '\n';
    return 0;
}

Measured memory_bytes: 1792
#include<iostream>

using namespace std;

#define fast ios_base::sync_with_stdio(false);cin.tie(NULL)
#define ll long long
#define deb(x) cout<<"["<<#x<<"="<<x<<"]"<<"\n";
#define FOR(a,b) for(ll i=a;i<b;++i)
#define read(x) for(auto& i:x)cin>>i

class MAIN
{
	public:
		void run()
		{
			ll t=1;//cin>>t;
			while(t--)
			{
				ll n;cin>>n;
				cout<<(n==1?0:1);
				cout<<"\n";
			}
		}	
};

int main()
{
	fast;
	MAIN solution;
	solution.run();
	return 0;
}

Measured memory_bytes: 3664
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <string.h>
using namespace std; using ll = long long; using pll = pair<ll, ll>;
using vl = vector<ll>; using vll = vector<vl>; using vpll = vector<pll>;
int ctoi(char c) {
	switch (c) {
	case '0': return 0; case '1': return 1; case '2': return 2;
	case '3': return 3; case '4': return 4; case '5': return 5;
	case '6': return 6; case '7': return 7; case '8': return 8;
	case '9': return 9;  default: return 0;
	}
}
bool pairCompare(const pll firstElof, pll secondElof)
{
	return firstElof.second > secondElof.second;
}
//**Snippetリスト**//
//rep, vin, all//
//gcdlcm, isPrime, eratos, modinv, bitSearch, bitList, dfs, bfs, dijkstra, UnionFind, COM, digitDP//
ll i, j, k, l, m, n; ll N, M, K, H, W, L;
ll MOD = 1000000007; ll INF = 9999999999999; ll ans = 0;
vl flag, color; vll path; vl D;
//***********//
int main() {
	cin >> N >> K;
	vpll F(N);
	for (i = 0; i < N; i++) {
		cin >> F[i].first >> F[i].second;
	}
	sort(F.begin(), F.end(),pairCompare);
	priority_queue<pll> Q;
	vl C(N);
	for (i = 0; i < N; i++) {
		C[i] = 0;
	}
	ll P = 0;
	for (i = 0; i < K; i++) {
		Q.push(make_pair(F[i].second*(-1), F[i].first-1));
		P += F[i].second;
		C[F[i].first - 1]++;
	}
	ll V = 0;
	for (i = 0; i < N; i++) {
		if (C[i] > 0) V++;
	}
	ans = P + V * V;
	ll nowF = K;
	for (i = 0; i < K; i++) {
		//cout << Q.top().first << " " << Q.top().second << endl;
		if (C[Q.top().second] >= 2) {
			while (nowF < N && C[F[nowF].first-1] != 0) nowF++;
			if (nowF == N)break;
			C[Q.top().second]--;
			C[F[nowF].first - 1]++;
			P -= Q.top().first * (-1);
			P += F[nowF].second;
			V++;
			ans = max(ans, P + V * V);
			nowF++;
		}
		//cout << P + V * V << endl;
		Q.pop();
	}
	cout << ans;
}
	


Measured memory_bytes: 4724
//コンパイラ最適化用
#pragma GCC optimize("Ofast")
//インクルード(アルファベット順)
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<chrono>//実行時間計測
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm,accumulate
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//順序保持しないmap
#include<unordered_set>//順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
typedef long long ll;

signed main(){
/*
  cin >> N;
  vector<int> a(N);
  for (int i = 0; i < N; i++)
    cin >> a[i];
*/
  int N, K;
  cin >> N;

  if (N % 1000 != 0)
    cout << 1000 - N % 1000 << endl;
  else
    cout << 0 << endl;
  return 0;
}

Measured memory_bytes: 3656
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
int main(){
    ll n,k;
    cin>>n>>k;
    ll ans=0;
    for(ll i=k;i<=n+1;i++){
        ll l=i*(i-1)/2;
        ll r=(n+n-i+1)*i/2;
        ans=(ans+r-l+1)%mod;
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 3644
H,W = map(int,input().split())
A = [input() for _ in range(H)]
MOD = 10**9+7

dp = [[0 for _ in range(W)] for _ in range(H)]
dp[0][0] = 1

for i in range(H):
  for j in range(W):
    if A[i][j] == '#':
      dp[i][j] = 0
    else:
      if j > 0:
        dp[i][j] += dp[i][j-1]
      if i > 0:
        dp[i][j] += dp[i-1][j]
    dp[i][j] %= MOD

print(dp[H-1][W-1])

Measured memory_bytes: 54364
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pci pair<char, int>
#define pic pair<int, char>
#define plvl pair<long long, vector<long long> >
#define pcvc pair<char, vector<char> >
#define mod 1000000007
#define newl "\n"

using namespace std;

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

template <typename T>
void show1(vector<T> dp) {
	for(auto d : dp) {
		cout << d << " ";
	}
	cout << "\n";
}

template <typename T>
void show2(vector<vector<T> > dp) {
	for(auto d : dp) {
		for(auto dd : d) {
			cout << dd << " ";
		}
		cout << "\n";
	}
}

void executeCode() {
	ll x;
	cin >> x;
	cout << (x >= 30 ? "Yes" : "No") << newl;
}

int main() {
	ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
	int tt = 1;
	// cin >> tt;
	for(ll i = 1; i <= tt ; i++) {
	//	cout << "Case #" << i << ": ";
		executeCode();	
	}
	return 0;
}

Measured memory_bytes: 3612
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define double long double
#define low lower_bound
#define upp upper_bound
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define Rep(i,n) for (int i = (int)(n); i >= 0; i--)
#define all(vec) vec.begin(),vec.end()
#define rever(vec) reverse(all(vec));
#define cend cout << endl;
#define prique(T) priority_queue<T,vector<T>,greater<T>>
struct edge { int to, cost; };
typedef pair<int, int> P;
const int mod = 1e9 + 7, inf = 1e16;

int modpow(int x, int n) {
	if (n == 0) return 1;
	if (n % 2) return (x * modpow(x * x % mod, n / 2) % mod + mod) % mod;
	return (modpow(x * x % mod, n / 2) + mod) % mod;
}

int fact(int n) {
	int ans = 1;
	rep(i, n) {
		ans *= (i + 1);
		ans %= mod;
	}
	return (ans + mod) % mod;
}

int comb(int n, int r) {
	if (n < r) swap(n, r);
	if (n - r < r) r = n - r;
	return (fact(n) * modpow(fact(n - r), mod - 2) % mod * modpow(fact(r), mod - 2) + mod) % mod;
}

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

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

bool pri(int p) {
	for (int i = 2; i * i <= p; i++) if (p % i == 0) return false;
	return p > 1;
}

int n;
int a[22];
int ans;
signed main() {
	cin >> n;
	rep(i, n) {
		cin >> a[i];
	}
	rep(i, n - 2) {
		if (a[i + 1] != max({ a[i],a[i + 1],a[i + 2] }) && a[i + 1] != min({ a[i],a[i + 1],a[i + 2] })) {
			ans++;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
n = int(input())  #一応読むけど、ループ回せば不要では
aList=list(map(int,input().split()))

aList.sort(reverse = True)

ap = 0
bp = 0

for i,a in enumerate(aList):
    if i%2 == 0: #0から始まるので偶数奇数逆で考える
        ap = ap + a
    else:
        bp = bp + a
print(ap-bp)

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

int main(){
    int n;
    cin >> n;
    vector<int> p(n);

    for (auto i = 0; i < n; i++)
    {
        int pi;
        cin >> pi;
        pi -= 1;
        p[i] = pi;
    }

    vector<long long> num(n);
    vector<long long> num_r(n);
    
    num[0] = 1;
    num_r[0] = 1;


    for (auto i = 1; i < n; i++)
    {
        num[i] = num[i - 1] + 10001;
        num_r[i] = num_r[i - 1] + 10001;
    }

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

    for (auto i = 0; i < n; i++)
    {
        if(i % 2 == 0){
            num[p[i]] += i / 2;
            num_r[p[i]] += i / 2;
        }else{
            num[p[i]] += (i + 1) / 2;
            num_r[p[i]] += i - ((i + 1) / 2);
        }
    }
    for (auto i = 0; i < n; i++)
    {
        cout << num[i] << " ";
    }

    cout << endl;

    for (auto i = 0; i < n; i++)
    {
        cout << num_r[i] << " ";
    }
    cout << endl;
}

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

int main() {
  int n, counter = 0;
  // vector<int> a;

  cin >> n;
  for (int i = 1; i <= n; i++) {
    int tmp;
    cin >> tmp;
    // a.push_back(tmp);
    if (tmp % 2 == 1 && i % 2 == 1) {
      counter++;
    }
  }
  cout << counter << endl;
  return 0;
}

Measured memory_bytes: 3640
def main
  x,n = gets.chomp.split(" ").map(&:to_i)
  ps = gets.chomp.split(" ").map(&:to_i)

  i = 0
  loop do
    target = x - i
    unless ps.include? target
      puts target
      return
    end
    target = x + i
    unless ps.include? target
      puts target
      return
    end
    i += 1
  end
end

main



Measured memory_bytes: 14316
# -*- coding: utf-8 -*-

N = int(input())
aN = [int(input()) for i in range(N)]

start = aN[0]
ans = -float('inf')
for i in range(1,N):
    # 今-起点と今までの最大を比較
    ans = max(aN[i] - start, ans)
    # 最安値の更新したら起点を変える
    start = min(aN[i], start)
print(ans)


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

#define pb push_back
#define For(i, j, k) for(int i = j; i <= k; i++)

using namespace std;

const int N = 1e5 + 10;

int n;
int dp[N];
vector<int> G[N];

void DFS(int o, int f = 0){
	int cnt = 0;
	for(int v : G[o]){
		if(v == f) continue;
		DFS(v, o);
		dp[o] += dp[v];
		cnt += !dp[v];
	}
	dp[o] += max(0, cnt - 1);

	if(!f && int(G[o].size()) - cnt <= 1 && cnt <= 1) ++dp[o];
}

int main(){

	scanf("%d", &n);
	For(i, 2, n){
		int u, v;
		scanf("%d%d", &u, &v);
		++u, ++v;
		G[u].pb(v), G[v].pb(u);
	}

	DFS(1);
	printf("%d\n", dp[1]);

	return 0;
}

Measured memory_bytes: 13824
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c;
    int x;
    cin>>a>>b>>c;
    if(c>a&&c>b)
    {
        x=a+b;
        if(x==c)
        {
            cout<<"Yes";
        }
        else
            cout<<"No";
    }
    else if(b>a&&b>c)
    {
        x=a+c;
        if(x==b)
        {
            cout<<"Yes";
        }
        else
            cout<<"No";
    }
    else if(a>b&&a>c)
    {
        x=b+c;
        if(x==a)
        {
            cout<<"Yes";
        }
        else
            cout<<"No";
    }
    else
        cout<<"No";


    return 0;
}


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

using namespace std;

#define FOR(i, n) for(int i = 0; i < (int) n; i++)
#define PB push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define F first
#define S second

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

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

	int h, w, k; cin >> h >> w >> k;
	vector<string> v(h);
	FOR(i, h) cin >> v[i];

	ll ans = 0;

	for(int i = 0; i < (1<<h); i++){
		for(int j = 0; j < (1<<w); j++){
			int cnt = 0;
			FOR(r, h){
				FOR(c, w){
					if( ((1<<r)&i) || ((1<<c)&j) ) continue;
					cnt+=(v[r][c] == '#');
				}
			}
			if(cnt == k) ans++;
		}
	}

	cout << ans << '\n';

	return 0;
}


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

int H[100005], dp[100005];

int absdif(int a, int b)
{
    if (a >= b) return(a - b);
    return(b - a);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, K;
    cin >> N >> K;
    for (int i = 1; i <= N; i++) cin >> H[i];
    dp[N] = 0;
    for (int i = N - 1; i; i--)
    {
        dp[i] = 1000000005;
        int lim = min(i + K, N);
        for (int j = i + 1; j <= lim; j++) dp[i] = min(dp[i], absdif(H[i], H[j]) + dp[j]);
    }
    cout << dp[1] << '\n';
    return(0);
}

Measured memory_bytes: 1024
#include<iostream>
#include<string>
using namespace std;
int main(void){
	string s;
	cin>>s;
	int ans=0;
	for(int i=0;i<s.size();i++){
		if(s[i]=='1'){
			ans++;
		}
	}
cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
			Scanner sc = new Scanner(System.in);
			
			while(sc.hasNext()){
				int d = sc.nextInt();
				int sq = 0;
				
				for(int t = d; t <= 600 - d; t = t + d){
					sq = sq + t * t * d;
				}
				
				System.out.println(sq);
			}
	}
}

Measured memory_bytes: 12000
#include<stdio.h>
struct UF{
  int u[10001];
  void init(int x){
    for(int i=0;i<x;i++){
      u[i] = i;
    }
  }
  int unite(int x,int y){
    x = find(x);
    y = find(y);
    if(x > y) u[x] = y;
    if(y > x) u[y] = x;
  }
  int find(int x){
    if(x != u[x]) u[x] = find(u[x]);
    return u[x];
  }
};
int main(){
  UF uf;
  int n,q,a,b,c;
  scanf("%d %d",&n,&q);
  uf.init(n);
  for(int i=0;i<q;i++){
    scanf("%d %d %d",&a,&b,&c);
    if(a) printf("%d\n",uf.find(b)==uf.find(c));
    if(!a) uf.unite(b,c);
  }
  return (0);
}

Measured memory_bytes: 2756
char m[110];int a[101],b[101];
char *T="abcdefghijklmnopqrstuvwxyz";
#define X(n) m[n]=T[(strchr(T,m[n])-T+b[i]-a[i])%26],
main(N,i,c){
  for(;scanf("%d",&N),N;printf("%s\n",m+1)){
    for(scanf("%s",m+1),i=1;i<=N;i++)scanf("%d%d",a+i,b+i);
    for(i=N;i;i--)X(a[i])X(b[i])c=m[a[i]],m[a[i]]=m[b[i]],m[b[i]]=c;
  }
}

Measured memory_bytes: 0
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <cmath>
#include <limits>
#include <list>
#include <cassert>
#define ALL(x) (x).begin(),(x).end()
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define int_INF 2147483647
#define pint_INF 2000000000
#define ll_INF 	9223372036854775807
#define MOD 1000000007
#define vi vector<int>
#define vvi vector<vector<int>>
#define vvll vector<vector<long long>>
#define vvc vector<vector<char>>
#define vll vector<long long>
#define pii pair<int,int>
#define vpii vector<pair<int,int>>
#define sysp system("PAUSE")
#define pno cout << "no" << endl
#define pyes cout << "yes" << endl
#define pYes cout << "Yes" << endl
#define pNo cout << "No" << endl
#define pNO cout << "NO" << endl
#define pYES cout << "YES" << endl
#define endl "\n"
#define pi 3.14159265358979
using namespace std;
using ll = long long;

int main(){
    string s; cin >> s;
    vector<char> vec(s.size());
    rep(i,s.size()) vec[i] = s[i];
    bool flag = false;
    vi ans = {-1,-1};
    if(s.size() > 2){
        for(int i = 2; i < s.size(); i++){
            if(vec[i] == vec[i-1]){
                true;
                ans = {i,i+1};
                break;
            }
            if(vec[i] == vec[i-2]){
                true;
                ans = {i-1,i+1};
                break;
            }
        }
    }else{
        if(vec[0] == vec[1]){
            ans = {1,2};
        }
    }
    

    cout << ans[0] << " " << ans[1] << endl;
    sysp;
}

Measured memory_bytes: 3916
program many_slimes
  implicit none
  integer :: n, m, s(262144) = 0, i, j
  integer :: x(262144) = 0, nx = 1, y(131072), ny
  read(*,*) n
  m = 2**n
  read(*,*) s(1:m)
  call bitonic_sort(s(1:m),.false.)
  x(1) = s(1)
  s(1) = -1
  do i = 1, n
    y(1:nx) = x(1:nx)
    ny = nx
    call bitonic_sort(y(1:ny),.true.)
    do j = 1, m
      if (s(j) < 0) cycle
      if (s(j) < y(ny)) then
        nx = nx+1
        x(nx) = s(j)
        s(j) = -1
        ny = ny-1
        if (ny == 0) exit
      end if
    end do
    if (ny > 0) then
      write(*,'(a)') "No"
      stop
    end if
  end do
  write(*,'(a)') "Yes"
contains
  recursive subroutine bitonic_sort(a,ascend)
    integer, intent(inout) :: a(:)
    logical, intent(in) :: ascend
    integer :: n
    n = size(a)
    if (n == 1) return
    call bitonic_sort(a(1:n/2),.not.ascend)
    call bitonic_sort(a(n/2+1:n),ascend)
    call bitonic_merge(a,ascend)
  end
  recursive subroutine bitonic_merge(a,ascend)
    integer, intent(inout) :: a(:)
    logical, intent(in) :: ascend
    integer :: n, m, i, b
    n = size(a)
    if (n == 1) return
    m = 1
    do while (2*m < n)
      m = 2*m
    end do
    do i = 1, n-m
      if ((a(i) > a(i+m)) .eqv. ascend) then
        b = a(i)
        a(i) = a(i+m)
        a(i+m) = b
      end if
    end do
    call bitonic_merge(a(1:m),ascend)
    call bitonic_merge(a(m+1:n),ascend)
  end
end program many_slimes

Measured memory_bytes: 3328
#include <iostream>

using namespace std;

int main(){
    long A, B, K, t;
    cin >> A >> B >> K;
    for(int i = 1; i <= K; i++){
        if(i%2 == 1){
            if(A%2 == 1)A--;
            B = B + A/2;
            A = A/2;
        }else{
            if(B%2 == 1)B--;
        A = A + B/2;
        B  = B/2;
        }
    }
    cout << A << ' ' << B << endl;
}

Measured memory_bytes: 256
#include <iostream>

int main() {
  int H, R;
  std::cin >> H >> R;
  
  if (H + R > 0) {
    std::cout << "1" << std::endl;
  } else {
    std::cout << (H + R == 0 ? "0" : "-1") << std::endl;
  }
}

Measured memory_bytes: 3088
package main

import (
	"bufio"
	"fmt"
	"os"
)

const mod = 998244353

func main() {
	r := bufio.NewReader(os.Stdin)

	var n, s int
	fmt.Fscanf(r, "%d %d\n", &n, &s)

	a := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Fscanf(r, "%d", &a[i])
	}

	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, s+1)
	}

	tot := 0
	for i := 0; i < n; i++ {
		for k := 1; k <= s; k++ {
			if i > 0 {
				dp[i][k] += dp[i-1][k]
				dp[i][k] %= mod
				if a[i] < k {
					dp[i][k] += dp[i-1][k-a[i]]
					dp[i][k] %= mod
				}
			}
			if a[i] == k {
				dp[i][k] += i + 1
				dp[i][k] %= mod
			}
		}
		tot += dp[i][s]
		tot %= mod
	}

	fmt.Println(tot)
}


Measured memory_bytes: 75392
#include<cstdio>
#include<algorithm>
const int MAXN=200005;

int a[MAXN];
int d[MAXN];

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    d[1]=a[1];
    int len=1;
    for(int i=2;i<=n;i++)
    {
        if(a[i]<=d[len])
            d[++len]=a[i];
        else
        {
            int j=std::lower_bound(d+1,d+len+1,a[i])-d;
            d[j]=a[i];
        }
    }
    printf("%d",len);
    return 0;
}


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

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();}
template<class T> inline T sqr(T x) {return x*x;}

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 pb push_back
#define each(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define exist(s,e) ((s).find(e)!=(s).end())
#define range(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  range(i,0,n)
#define clr(a,b) memset((a), (b) ,sizeof(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

const double eps = 1e-10;
const double pi  = acos(-1.0);
const ll INF =1LL << 50;
const int inf = 1 << 30;

int n,m;
int hp[110];

const ll hpmax=100000;

ll single[100010];
ll all[100010];


int main(void){
	while(cin >> n,n){
		rep(i,n) cin >> hp[i];
		cin >> m;
		rep(i,100010) single[i]=INF,all[i]=INF;
		single[0]=all[0]=0LL;
		rep(i,m){
			string _,type;
			ll mp,damage;
			cin >> _ >> mp >> type >> damage;
			if(type=="Single"){
				rep(j,hpmax+1){
					ll ndamage=min(damage+j,hpmax);
					single[ndamage]=min(single[ndamage],single[j]+mp);
				}
			}else{
				rep(j,hpmax+1){
					ll ndamage=min(damage+j,hpmax);
					all[ndamage]=min(all[ndamage],all[j]+mp);
				}
			}
		}
		for(int i=hpmax;i>=0;i--){
			single[i]=min(single[i],single[i+1]);
			all[i]=min(all[i],all[i+1]);
		}
		ll ans=INF;
		rep(i,hpmax+1){
			ll cur=all[i];
			rep(j,n){
				int index=max(0,hp[j]-i);
				cur+=single[index];
			}
			ans=min(ans,cur);
		}
		cout << ans << endl;
	}
	return 0;
}

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

ll n, k, arr[1000001];
ll dp_arr[1000001];

ll dp(ll i) {
    if (i == n) {
        return dp_arr[i] = 0;
    } else if (dp_arr[i] != -1) {
        return dp_arr[i];
    } else {
        ll least = 1000000000;
        for (ll j = 1; j <= min(k, n - i); j++) {
            least = min(least, dp(i + j) + abs(arr[i + j] - arr[i]));
        }
        return dp_arr[i] = least;
    }
}

int main() {
    cin >> n >> k;
    dp_arr[0] = -1;
    for (ll i = 1; i <= n; i++) {
        cin >> arr[i];
        dp_arr[i] = -1;
    }
    return cout << dp(1) << '\n', 0;
}

Measured memory_bytes: 9856
#include<bits/stdc++.h>
using namespace std;
int main(){
  double a,b,h,m;
  cin>>a>>b>>h>>m;
  h*=5*6;
  h+=m/2;
  m*=6;
  m=abs(h-m);
  if(m>180)m=360-m;
  m=M_PI*m/180;
  double ans;
  ans=a*a+b*b-2*a*b*cos(m);
  ans=sqrt(ans);
  cout<<fixed<<setprecision(21)<<ans<<endl;
  return 0;
}


Measured memory_bytes: 4212
def LI(): return [int(x) for x in input().split(" ")]
def LS(): return [str(x) for x in input().split(" ")]
def ItoS(L): return [str(x) for x in L]
def StoI(L): return [int(c) for c in L]


def solve():
    x, y = LI()
    ans = 0

    while x <= y:
        ans += 1
        x *= 2

    print(ans)

solve()

Measured memory_bytes: 3060
#include <bits/stdc++.h>
typedef long long int ll;
using namespace std;
int main(){
  ll n;
  cin >>n;
  ll s;
  vector <ll> a;
  vector <pair<ll,ll>> ee;
  for(ll i=0;i<n;i++) {
    cin >>s;
    a.push_back(s);
    a.push_back(s+1);
    a.push_back(s-1);
  }
  sort(a.begin(),a.end());
  ll c=1;
  for(ll i=0;i<3*n;i++){//配列の中身がそれぞれ何個あるかのカウント
   if(a[i]==a[i+1]){
     c++;
     if(i==3*n-2){//122333みたいなときは3のところがansに入らないので
       ee.push_back(make_pair(c,a[i]));
       break;
     }
   }
   else{
     ee.push_back(make_pair(c,a[i]));
     if(i==3*n-2) {
         ee.push_back(make_pair(1,a[i+1]));//112223とかのときにansに3の分を足すため
         break;
     }
     c=1;
   }
 }
 sort(ee.begin(),ee.end());
 cout <<ee[ee.size()-1].first<<endl;
}


Measured memory_bytes: 7788
'use strict';

function Main(input) {
    const tmp = input.trim().split('\n');
    const [N, M, K] = tmp[0].split(' ').map((v) => Number(v));
    const A = tmp[1].split(' ').map((v) => Number(v));
    const B = tmp[2].split(' ').map((v) => Number(v));

    let readBooksNums = [];

    // A=0冊
    let timeB = 0;
    let countB = 0;
    for (let i = 0; i < M; i++) {
        if (K - timeB < B[i]) {
            break;
        }
        timeB += B[i];
        countB++;
    }
    readBooksNums.push(countB);

    // A=1冊〜
    let timeA = 0;
    for (let i = 0; i < N; i++) {
        if (K - timeA < A[i]) {
            break;
        }
        timeA += A[i];
        const remain = K - timeA;
        if (remain < timeB && countB !== 0) {
            for (let j = countB - 1; j >= 0; j--) {
                timeB -= B[j];
                countB -= 1;
                if (remain >= timeB) {
                    break;
                }
            }
        }
        readBooksNums.push(countB + i + 1);
    }

    const result = readBooksNums.reduce((a, b) => Math.max(a, b));

    console.log(String(result));

    return;
}
Main(require('fs').readFileSync('/dev/stdin', 'utf8'));

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

int main() {
  int n;
  int f;
  cin>>n;
  int tmp=n;
  while(tmp>0){
    f+=tmp%10;
    tmp/=10;
  }
  if(n%f==0)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}

Measured memory_bytes: 3612
import java.util.Scanner;
 
public class Main {
 
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    long N = sc.nextLong();
    long K = sc.nextLong();
    long ans;
    if (K <= N) {
    	ans = (N%K) < (K - N%K) ? N%K : (K - N%K);
    } else {
    	ans = N < (K - N) ? N : (K - N);
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 21844
alpha_dict = {}
for i,c in enumerate(range(ord('A'),ord('Z')+1)):
  alpha_dict[chr(c).lower()] = 0

s = list(input())
for i in range(len(s)):
  alpha_dict[s[i]] += 1

for k, v in alpha_dict.items():
  if v == 0:
    print(k)
    exit()
print('None')

Measured memory_bytes: 77380
n, m = map(int, input().split())
ans = [-1 for _ in range(n)]
end_flag = False
for _ in range(m):
    s, c = map(int, input().split())
    if ans[s-1] == -1:
        ans[s-1] = c
    elif ans[s-1] == c:
        continue
    else:
        end_flag = True
        break
# print(ans)
if ans[0] == 0 and n > 1:
    end_flag = True
if ans[0] == -1:
    if n > 1:
        ans[0] = 1
    else:
        ans[0] = 0

for i in range(1, n):
    if ans[i] == -1:
        ans[i] = 0
# print(ans)
if end_flag:
    print(-1)
else:
    ss = ''
    for i in ans:
        ss = ss + str(i)
    print(ss)


Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <math.h>
#include <iomanip>
using namespace std;
typedef long long int ll;
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll N, M, R, a, b, c, r[9], dis[210][210] = {}, inf = 1e9;
	cin >> N >> M >> R;
	for (int i = 0; i < N; i++)for (int j = i + 1; j < N; j++)dis[i][j] = dis[j][i] = inf;
	for (int i = 0; i < R; i++)cin >> r[i];
	for (int i = 0; i < M; i++) {
		cin >> a >> b >> c;
		a--; b--;
		if (dis[a][b] > c)dis[a][b] = dis[b][a] = c;
	}
	for (int k = 0; k < N; k++)for (int i = 0; i < N; i++)for (int j = 0; j < N; j++)dis[i][j] = min(dis[i][k] + dis[k][j], dis[i][j]);
	sort(r, r + R);
	ll num = 0, ans = inf;
	do {
		for (int i = 0; i < R - 1; i++)num += dis[r[i] - 1][r[i + 1] - 1];
		ans = min(ans, num);
		num = 0;
	} while (next_permutation(r, r + R));
	cout << ans << endl;
	return 0;
}

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

using ll=long long;
const ll MOD=1000000007;

int main() {
  int N,K;
  cin >> N >> K;
  if(N%K==0){
    cout << 0 << endl;
  }
  else
    cout << 1 << endl;
}

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

int main(){
	int n;
	cin>>n;
	
	int ma=0;
	int mi=1001;
	for(int i=0;i<n;i++){
		int a;
		cin>>a;
		ma=max(ma,a);
		mi=min(mi,a);
	}
	
	cout<<ma-mi<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vl vaector<long>
#define vll vector<long long int>
#define vC  vector<char>
#define FastIO ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define db(...) ZZ(#__VA_ARGS__, __VA_ARGS__)
ll pow(ll x, ll y,ll m) { ll res = 1;x=x%m; while (y > 0) { if (y & 1) res = ((res%m) * (x%m))%m; y = y >> 1; x = ((x%m) * (x%m))%m; } return res%m; }
template <typename Arg1> void ZZ(const char* name, Arg1&& arg1){std::cerr << name << " = " << arg1 << endl;}
template <typename Arg1, typename... Args>void ZZ(const char* names, Arg1&& arg1, Args&&... args)
{
	const char* comma = strchr(names + 1, ',');
	std::cerr.write(names, comma - names) << " = " << arg1;
	ZZ(comma, args...);
}
const ll INF = 0xFFFFFFFFFFFFFFFL;
clock_t time_p=clock();
void abhigyan10()
{time_p=clock()-time_p;cerr<<"Time Taken : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";}
ll seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline ll rnd(ll l=0,ll r=INF){return uniform_int_distribution<ll>(l,r)(rng);}
#define clrbuf cin.ignore(numeric_limits<streamsize>::max(),'\n');
#define preciset(x) cout<<setprecision(x)<<fixed;
const ll mod =1000000007;
int main()
{
        FastIO
        int n,k,i,d=0;

        cin>>k>>n;
        vi a(n);
        for(i=0;i<n;i++) cin>>a[i];

        sort(a.begin(),a.end());
    	d= k-a[n-1] + a[0];
    	for(i=0;i<n-1;i++)
    	{
    		d= max(a[i+1]-a[i],d);
    	}

    	cout<<k-d;
    	return 0;
    }

Measured memory_bytes: 1024
def show(A):
    L = list(map(str, A))
    print(" ".join(L))

N = int(input())
A = list(map(int, input().split()))
cnt = 0

for i in range(0, N):
    minj = i
    for j in range(i, N):
        if A[j] < A[minj]:
            minj = j
    if A[i] != A[minj]:
        cnt += 1
        A[i], A[minj] = A[minj], A[i]
    
show(A)
print(cnt)


Measured memory_bytes: 5600
S = input()
if(S == "SUN"):
  print(7)
elif(S == "MON"):
  print(6)
elif(S == "TUE"):
  print(5)
elif(S == "WED"):
  print(4)
elif(S == "THU"):
  print(3)
elif(S == "FRI"):
  print(2)
elif(S == "SAT"):
  print(1)

Measured memory_bytes: 3060