akhauriyash/Code-Regression huggingface dataset:
K , N = map(int,input().split())
A = list(map(int,input().split()))
M = 0
a = A[0] 
for i in range(N-1):
    if M < A[i+1] - a:
        M = A[i+1] - a
    a = A[i+1]
if M < K - A[N-1] + A[0]:
    M = K - A[N-1] + A[0]
print(K-M)

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

int main() {
  int N;
  int ans = 1;
  int b = 0;
  
  cin >> N;
  vector<int> vec(N);
  vector<bool> check(N);

  for(int i=0;i<N;++i){
    cin >> vec.at(i);
  }
  while(vec.at(b) != 2){
    if(check.at(b) == true){
      cout << -1 << endl;
      return 0;
    }else{
      ans += 1;
      check.at(b) = true;
      b = vec.at(b) - 1;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3792
n, q = gets.split.map(&:to_i)
s = gets.chomp
ans = 0
dp = Array.new(n,0)
for i in 0..s.size-1 do
  dp[i] = dp[i-1].to_i
  if s[i..i+1] == 'AC'
    dp[i] += 1
  end
end

q.times do |i|
  l, r = gets.split.map(&:to_i)
  lt = l < 2 ? 0 : dp[l-2]
  puts dp[r-2] - lt
end


Measured memory_bytes: 3452
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define endl '\n'

void solvetask(){
    string s; cin >> s;
    int ans = 0;
    for (int i=0, cur = 0; i<s.size(); i++){
        if (s[i] == 'S') cur = 0;
        else cur++;
        ans = max(ans, cur);
    }
    cout << ans << endl;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t=1; //cin >> t;
    while(t--) solvetask();
}

Measured memory_bytes: 3580
# ContestName
# URL
import sys
#import numpy as np

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N, C = i2nn()
    D = ii2nnn(C)
    c = ii2nnn(N)
    E = [[0] * C for _ in range(3)]
    for i in range(N):
        for j in range(N):
            before = c[i][j]
            e = (i+j) % 3
            for after in range(1, C+1):
                E[e][after-1] += D[before-1][after-1]
    iwakan = N * N * 1000
    for c1 in range(C):
        for c2 in range(C):
            for c3 in range(C):
                if c1 == c2 or c2 == c3 or c3 == c1:
                    continue
                n = E[0][c1] + E[1][c2] + E[2][c3]
                if n < iwakan:
                    iwakan = n
    print(iwakan)

main()


Measured memory_bytes: 46812
//Coded by Abhijay Mitra
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <numeric>
#include <vector>
#include <iterator> 
#include <map>
#include <set>
#include <climits>
#include <queue>
#include <cmath>
#include <stack>
#include <cctype>
#include <bitset>
// #include <bits/stdc++.h>
#define double long double
#define int long long int
#define ll int
#define ibs ios_base::sync_with_stdio(false)
#define cti cin.tie(0)
#define bp __builtin_popcount
#define pb push_back
#define koto_memory(a) cout<<(sizeof(a)/1048576.0)<<" MB";
#define res(v) v.resize(unique(v.begin(), v.end()) - v.begin());
#define cnt_res(v) std::distance(v.begin(),std::unique(v.begin(), v.end())); 
#define timer cerr << "Time elapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << " sec \n";
using vi = std::vector<int>;
using vvi = std::vector<vi>;
using pii = std::pair<int,int>;
using vpii = std::vector<pii>;
using vvpii = std::vector<vpii>;
#define mp         make_pair
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define per(i,b,a) for (int i = b; i >= a; i--)
#define all(x)     x.begin(), x.end()
using namespace std;
const int N=2e6+10;
const int inf = /*0x3f3f3f3f*/1e18+10;
// const ll M = 998244353 ; // Mulo
// const int M = 1e9+7 ; // Mulo
const double Pi = 3.14159265;
#define F first
#define S second
int n,a[N];string s;
void solve(){
  cin>>n;if(n%1000)
  cout<<1000-n%1000;
  else cout<<0;
}
int32_t main()
{
  ibs;cti;
  solve()
  /*,cout<<"\n"*/;
  // cout<<"\n";
  int xx=0;
  // int t;cin>>t;while(t--){/*xx++;cout<<"Case "<<xx<<":\n"*/;solve();cout<<"\n";}
  return 0;
}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N;
    cin >> N;
    string S;
    cin >> S;
    char a;
    int ans = 0;
    for(int i = 0; i < N; i++){
        if(i == 0){
            a = S[i];
        }
        if(i != 0){
            if(a == S[i]){
                ans++;
            }
            else{
                a = S[i];
            }
        }
    }
    cout << N - ans << endl;
    return 0;
}

Measured memory_bytes: 512
import math
N = int(input())
l = [int(i) for i in input().split()]
#print(len(l))
A = []
x = 0
X = sum(l)
ans = 100000000000000

for i in range(N):
	x += l[i]
	if i + 1 < N:
		ans = min(ans,int(math.fabs(X-2*x)))


 
	
#print(int(sum/2))
#print(x,y)
print(ans)


Measured memory_bytes: 23800
//
//  main.cpp
//  112
//
//  Created by 耿英俊 on 2019/10/27.
//  Copyright © 2019 耿英俊. All rights reserved.
//

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main(int argc, const char * argv[]) {
    int a,b;
    while(cin>>a>>b){
        if(a<=9&&b<=9){
            cout<<a*b<<endl;
        }
        else
            cout<<"-1"<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;

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

const ll MOD=1e9+7;
const ll INF=1e18;
const double pi=acos(-1);
const double eps=1e-10;

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

int main(){
    while(1){
        int n, m; cin>>n>>m;
        if(n == 0) return 0;
        vector<int> s(n), d(m);
        for(int i=0; i<n; i++) cin>>s[i];
        for(int i=0; i<m; i++) cin>>d[i];

        int cur = 0;
        for(int i=0; i<m; i++){
            cur += d[i];

            if(n - 1 <= cur){
                cout << i + 1 << endl;
                break;
            }

            cur += s[cur];

            if(n - 1 <= cur){
                cout << i + 1 << endl;
                break;
            }
        }
    }
}


Measured memory_bytes: 2996
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll A[200009],B[200009];
vector<pair<ll,ll> >vec;
int main()
{
    ll a,b,c,d,e,i,j,k,l,n,m,x,y,t,p;
    scanf("%lld",&n);
    for(i=0;i<n;i++)
    {
        scanf("%lld",&A[i]);
    }
    for(i=0;i<n;i++)
    {
        scanf("%lld",&B[i]);
    }
    sort(B,B+n,greater<ll>());
    for(i=0;i<n;i++)
    {
        if(A[i]==B[i])
        {
            vec.push_back({A[i],i});
        }
    }
    l=vec.size();
    j=0;
    for(i=0;i<n;i++)
    {
        if(j==l)
        {
            break;
        }
        if(A[i]!=vec[j].first && B[i]!=vec[j].first)
        {
            swap(B[i],B[vec[j].second]);
            j++;
        }
    }
    if(j==l)
    {
        printf("Yes\n");
        for(i=0;i<n;i++)
        {
            printf("%lld ",B[i]);
        }
        printf("\n");
    }
    else
    {
        printf("No\n");
    }
}


Measured memory_bytes: 10492
#include<iostream>
#include<set>
#include<string>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<map>
using namespace std;

int N,P;

const int TIME = 30;

struct T{
  int day,s;
  string name;
  bool f;
  T(){f = false;};
  bool operator < (const T&t)const{
    if(day == t.day)return s < t.s;
    return day < t.day;
  }
};

vector<T>vec;
vector<pair<int,pair<int,int> > >vec2;
set<string>st;

void init(){
  vec.clear();
  st.clear();
  vec2.clear();
}

void input(){
  for(int i = 0 ; i < N ; i++){
    T t;
    cin >> t.name >> t.day;
    string tmp,h,m;
    cin >> tmp;
    for(int j = 0 ; j < tmp.size() ; j++){
      if(j < 2)m += tmp[tmp.size()-1-j];
      else h += tmp[tmp.size()-1-j];
    }
    reverse(m.begin(),m.end());
    reverse(h.begin(),h.end());
    t.s = atoi(m.c_str()) + atoi(h.c_str())*60;
    vec.push_back(t);
  }
  cin >> P;
  for(int i = 0 ; i < P ; i++){
    string str; cin >> str;
    st.insert(str);
  }
}

bool check(int day,int s,int e,int id){
  for(int i = 0 ; i < vec2.size() ; i++){
    if(id == i)continue;
    if(day != vec2[i].first)continue;
    pair<int,int> p = vec2[i].second;
    if(p.first <= s && s < p.second)return true;
    if(p.first < e && e <= p.second)return true;
    if(s == p.first && p.second == e)return true;
  }
  return false;
}

int solve(){
  init();
  input();
  sort(vec.begin(),vec.end());

  /*
  for(int i = 0 ; i < vec.size() ; i++){
    cout << "name = " << vec[i].name << ' ' << vec[i].day << ' ' << vec[i].s << ' ' << vec[i].s + TIME << endl;
  }
  */

  for(int i = 0 ; i < vec.size() ; i++){
    if(st.count(vec[i].name)){
      vec2.push_back(make_pair(vec[i].day,make_pair(vec[i].s,vec[i].s + TIME)));
      vec[i].f = true;
    }
  }

  for(int i = 0 ; i < vec2.size() ; i++){
    if(check(vec2[i].first,vec2[i].second.first,vec2[i].second.second,i))return -1;
  }

  int ret,day,now,pre;
  ret = day = now = 0;
  pre = -1;

  for(int i = 0 ; i < vec.size() ; i++){

    //cout << "i = " << i << " pre = " << pre << " day = "  << day << " now = " << now  << " ret = " << ret << endl;

    if(vec[i].f)continue;
    //cout << "#1" << endl;
    if(pre != vec[i].day){
      pre = vec[i].day;
      now = 0;
    }
    //cout << "#2" << endl;
    if(now > vec[i].s)continue;
    //cout << "#3" << endl;
    if(!check(vec[i].day,vec[i].s,vec[i].s + TIME,-1)){
      //cout << "name = " << vec[i].name << endl;
      ret++;
      now = vec[i].s + TIME;
    }
    //cout << "#4" << endl;
  }
  return ret + vec2.size();
}

int main(){
  while(cin >> N,N)cout << solve() << endl;
  return 0;
}

Measured memory_bytes: 1288
#include<iostream>
#include<stdio.h>
using namespace std;

int main()
{
	int n, m, x[100], key, i;

	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d", &x[i]);
	}

	scanf("%d", &m);
	for (i = 0; i < m; i++) {
		scanf("%d", &key);
		if (x[key-1]+1 != x[key] && x[key-1] != 2019) x[key-1] = x[key-1] + 1;
	}

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


Measured memory_bytes: 3152
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("sse4")

using namespace std;

#define FOR(a,b) for(int a=0;a<b;a++)
#define F0R(a,b,c) for(int a = b; a<=c; a++)
#define f first
#define s second
#define m0(x) memset(x,0,sizeof(x))

typedef pair<int,int> pi;
typedef long long ll;
typedef vector<int> vi;
typedef vector<pi> vpi;

const ll large = 1e15;

ll gcdExtended(ll a, ll b, ll *x, ll *y)
{
    // Base Case
    if (a == 0)
    {
        *x = 0, *y = 1;
        return b;
    }

    ll x1, y1; // To store results of recursive call
    ll gcd = gcdExtended(b%a, a, &x1, &y1);

    // Update x and y using results of recursive
    // call
    *x = y1 - (b/a) * x1;
    *y = x1;

    return gcd;
}

ll modinv(ll a, ll m)
{
    ll x, y;
    ll g = gcdExtended(a, m, &x, &y);
    if (g != 1)
        cout << "Inverse doesn't exist";
    else
    {
        ll res = (x%m + m) % m;
        return res;
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    ll n; cin >> n; n *= 2LL;
    if(n == 1){
        cout << "1\n";
        return 0;
    }
    vector<ll> divisors;
    int sq = sqrt(n);
    F0R(i,2,sq){
        if(n%i == 0) divisors.push_back(i);
        else continue;
        ll other = n/(ll)i;
        if(other > i) divisors.push_back(other);
    }
    ll ans = n-1;
    for(auto &a: divisors){
        ll other = n/a;
        if(__gcd(a,other) != 1) continue;
        ll c = modinv(other,a);
        if(log10(c)+log10(other) > 17) continue;
        c *= other;
        ans = min(ans,c-1);
    }
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 4052
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a,b;
  cin>>a>>b;
  if(a<10&&a>0){
    if(b<10&&b>0){
      cout<<a*b;
    }
    else{
      cout<<-1;
    }
  }
  else{
    cout<<-1;
  }
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)
	
	a := make([]int, n)
	b := make([]int, n-1)
	
	for i := range b {
		fmt.Scan(&b[i])
	}
	
	a[0] = b[0]
	for i := 1; i < n - 1; i++ {
		a[i] = min(b[i-1],b[i])
	}
	a[n-1] = b[n-2]
	
	sum := 0
	for i := range a {
		sum += a[i]
	}
	fmt.Println(sum)
}

func min(num1,num2 int)int {
	if num1 < num2 {
		return num1
	} else {
		return num2
	}
}

Measured memory_bytes: 512
#include <algorithm>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define rep(i, n) repd(i, 0, n)
typedef long long ll;

using namespace std;

template <typename T> void output(T, int);
int gcd(int a, int b);

int main() {
    // source
    int n, t;
    cin >> n >> t;
    int a[n];
    rep(i, n) { cin >> a[i]; }

    int dif = 0, num = 0;
    int l = a[0];

    repd(i, 1, n) {
        if (a[i] - l > dif) {
            dif = a[i] - l;
            num = 1;
        } else if (a[i] - l == dif) {
            num++;
        }

        l = min(l, a[i]);
    }

    cout << num << endl;
    return 0;
}

template <typename T> void output(T a, int precision) {
    if (precision > 0) {
        cout << setprecision(precision) << a << "\n";
    } else {
        cout << a << "\n";
    }
}

template <typename T> T min(T a, T b) {

    if (a < b) {
        return a;
    } else {
        return b;
    }
}

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


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const double pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
    REP(i,v.size()){if(i)os<<" ";os<<v[i];}return os;}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
    REP(i,v.size()){if(i)os<<endl;os<<v[i];}return os;}

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; }



int main(int argc, const char * argv[]) {
    
   
    
    int N,M; cin >> N >> M;
    vector<vector<int>> s(M);
    for (int i = 0; i < M; i++) {
        int k; cin >> k;
        s[i].resize(k);
        for (int j = 0; j < k; j++) {
            cin >> s[i][j];
            s[i][j]--;
            
        }
    }
    vector<int> p(M);
    for (int i = 0; i < M; i++) cin >> p[i];
    
    
    
    //culcurate
    int Ans = 0;
    //full search
    
    for (int bit = 0; bit < (1 << N); bit++) {
        bool isLightAllOn = true;
        
        
        
        
        
        for (int m = 0; m < M; m++) {
            int count = 0;
            for (int i = 0; i < (int)s[m].size(); i++) if(bit & (1 << s[m][i]) ) count++;
            if(count % 2 != p[m]) {
                isLightAllOn = false;
                break;
            }
        }
        
        if(isLightAllOn) Ans++;
        
        
        
        
        
        
        
    }
    
    cout << Ans << endl;
    
    
    
    
    
    
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

int digit_sum(int n)
{

	int ret = 0;
	while (n)
	{
		ret += n % 10;
		n /= 10;
	}
	return ret;
}

int main()
{
	cin.sync_with_stdio(false), cin.tie(nullptr);

	int n;
	cin >> n;

	int ans = 987654321;
	for (int i = 1; i < n; i++)
	{
		ans = min(ans, digit_sum(i) + digit_sum(n - i));
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 896
def min_count(nums):
    c = 0
    for i in range(len(nums)-2):
        if nums[i]<nums[i+1]<nums[i+2]:
            c = c + 1
        elif nums[i+2]<nums[i+1]<nums[i]:
            c = c + 1
    return c
a = input()
b = map(int,input().split())
c =[]
for x in b:
	c.append(x)
print(min_count(c))


Measured memory_bytes: 3060
#include<iostream>
#include<algorithm>
#include<string>
#include<math.h>
#include<vector>
#include<iomanip>
using namespace std;

int main(void)
{
    int count = 0;
    bool judge = true;
    string s;
    cin >> s;
    for(int i = s.size();;i--)
    {
        if(i % 2 != 0){continue;}
        for(int a = 0;a < i / 2;a++)
        {
            if(s[a] != s[i / 2 + a])
            {
                judge = false;
                break;
            }
        }
        if(judge && i < s.size()){cout << i << endl; break;}
        judge = true;
    }
    return 0;
}

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

int calc(vector<string>& S, int l, int r, int depth) {
    if (S[l][S[l].size() - 1] >= '0' && S[l][S[l].size() - 1] <= '9') {
        return S[l][S[l].size() - 1] - '0';
    }
    char op = S[l][S[l].size() - 1];
    vector<int> idx;
    for (int i = l + 1; i < r; i++) {
        if (S[i].size() == depth + 1) {
            idx.push_back(i);
        }
    }
    idx.push_back(r);
    int res = op == '+' ? 0 : 1;
    for (int i = 0; i < idx.size() - 1; i++) {
        if (op == '+') res += calc(S, idx[i], idx[i + 1], depth + 1);
        else res *= calc(S, idx[i], idx[i + 1], depth + 1);
    }
    return res;
}

void solve(int n) {
    vector<string> s(n);
    for (int i = 0; i < n; i++) cin >> s[i];
    cout << calc(s, 0, n, 1) << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    while (true) {
        cin >> N;
        if (N == 0) break;
        solve(N);
    }
    return 0;
}


Measured memory_bytes: 3136
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
constexpr int MOD = 1000000007;
constexpr int INF = numeric_limits<int>::max() / 2;
typedef pair<int,int> P;
using Graph = vector<vector<int>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
// cout << fixed << setprecision(14);
 
 
signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int N, A, B;
	cin >> N >> A >> B;
	if(abs(A-B) % 2 == 0){
		cout << "Alice" << endl;
	}
	else{
		cout << "Borys" << endl;
	}
}

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

int main()
{
	int a = 0, b = 0, c = 0, d = 0;
	cin >> a >> b >> c;
	for (int i = a; i <= b; i++) {
		if (c%i == 0)
			d++;
	}
	cout << d << endl;
	return 0;
}


Measured memory_bytes: 3092
/**
 *  author: MOOONI
 *  hackers are welcome!
**/
#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;

const int md = 998244353;

inline void add(int &a, int b) {
  a += b;
  while (a < 0) {
    a += md;
  }
  a %= md;
} 

inline int mul(int a, int b) {
  return (int) ((long long) a * b % md);
}

inline int power(int a, int b) {
  int res = 1;
  while (b) {
    if (b & 1) {
      res = mul(res, a);
    }
    a = mul(a, a);
    b >>= 1;
  }
  return res;
}

inline int inv(int a) {
  return power(a, md - 2);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m, k;
  cin >> n >> m >> k;
  vector<int> fact(n + 1);
  fact[0] = 1;
  for (int i = 1; i <= n; i++) {
    fact[i] = mul(fact[i - 1], i);
  }
  vector<int> inv_fact(n + 1);
  inv_fact[n] = inv(fact[n]);
  for (int i = n - 1; i >= 0; i--) {
    inv_fact[i] = mul(inv_fact[i + 1], i + 1);
  }
  auto C = [&](int n, int k) {
    if (k < 0 || k > n) {
      return 0;
    }
    return mul(fact[n], mul(inv_fact[k], inv_fact[n - k]));
  };
  int ans = 0;
  for (int i = 0; i <= k; i++) {
    add(ans, mul(C(n - 1, i), mul(m, power(m - 1, n - i - 1))));
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 4752
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* constant */
const int INF = 1 << 30;
const ll LINF = 1LL << 61;
const int NIL = -1;
const int MAX = 10000;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* global variables */
/* function */
/* main */
int main(){
    int n;
    cin >> n;

    int ans = 0;

    for (int i = 1; i < n; i++) {
        for (int j = 1; j * j <= i; j++) {
            if (i % j == 0) {
                ans++;
                if (j * j != i) ans++;
            }
        }
    }
    cout << ans << '\n';
}


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

using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair
#define loop(i,a,b) for(ull i=(a);i<ull(b);++i)
#define rep(i,n) loop(i,0,n)
#define iter(i,c) for(auto i=(c).begin(); i!=(c).end(); ++i)
#define riter(i,c) for(auto i=(c).rbegin(); i!=(c).rend(); ++i)
const double eps = 1e-10;
const double pi  = acos(-1.0);
const double inf = (int)1e8;
namespace std {
    template<typename T>ostream&operator<<(ostream&os, vector<T>const&v){
        iter(it,v) os<<*it<<(it+1==v.end()?"":",");
        return os;
    }
    template<typename T, typename U>ostream&operator<<(ostream&os,const pair<T,U>&p){
        return os << "[" << p.dirst << "," << p.second << "]";
    }
}

void visit(const vvi &g, int v, vvi& scc,
           stack<int> &S, vector<bool> &inS,
           vector<int> &low, vector<int> &num, int& time) {
    low[v] = num[v] = ++time;
    S.push(v); inS[v] = true;
    iter(e, g[v]) {
        int w = *e;
        if (num[w] == 0) {
            visit(g, w, scc, S, inS, low, num, time);
            low[v] = min(low[v], low[w]);
        } else if (inS[w])
            low[v] = min(low[v], num[w]);
    }
    if (low[v] == num[v]){
        scc.push_back(vi());
        while (1) {
            int w = S.top(); S.pop(); inS[w] = false;
            scc.back().push_back(w);
            if (v == w) break;
        }
    }
}
 
void scc(vvi const& g, vvi& res) {
    int const n = g.size();
    vi num(n), low(n);
    stack<int> S;
    vector<bool> inS(n);
    int time = 0;
    rep(u,n)if(num[u]==0) visit(g, u, res, S, inS, low, num, time);
}
 
int main(){
    int n;
    while(cin>>n,n){
        vvi g(n*n);
        rep(i,n)rep(j,n){
            int x,y; cin>>x>>y;
            int u=i*n+j;
            int v=y*n+x;
            g[u].push_back(v);
        }
        vvi ans;
        scc(g,ans);
        int c=0;
        rep(i,ans.size()){
            if(ans[i].size()==1){
                if(g[ans[i][0]][0]!=ans[i][0]) c++;
            }
        }
        cout << ans.size()-c << endl;
    }
}

Measured memory_bytes: 2396
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define N 500000

void mergeSort(int [ ], int , int);
void merge(int [ ], int , int , int );

int cnt=0;

int main()
{
  int i,S[N],n;

  while(1)
    {
      scanf("%d",&n);
      if(n <= N && n > 0) break;
    }

  for(i=0;i<n;i++)
      scanf("%d",&S[i]);

  mergeSort(S,0,n);

  for(i=0;i<n-1;i++)
    printf("%d ",S[i]);
  
  printf("%d\n%d\n",S[i],cnt);
  
  return 0;
}

void mergeSort(int A[ ], int left, int right)
{
  int mid;
  if(left+1 < right)
    {   
      mid = (left + right) / 2;
      mergeSort(A,left,mid);
      mergeSort(A,mid,right);
      merge(A,left,mid,right);
    }
}

void merge(int A[ ], int left, int mid, int right)
{
int i,j,k,n1,n2;
int *sl,*sr;

  n1 = mid - left;
  n2 = right - mid;

  sl = malloc(sizeof(int) * n1 + 1);
  sr = malloc(sizeof(int) * n2 + 1);
  
  for (i = 0; i < n1; i++)
    sl[i] = A[left + i];
  
  sl[n1] = (int)INFINITY;
  
  for (j = 0; j < n2;j++)
    sr[j] = A[mid + j];
  
  sr[n2] = (int)INFINITY;
  i = 0;         
  j = 0;       

  for (k = left; k < right; k++)
    {
      if (sl[i] <= sr[j])
	{
	  A[k] = sl[i];
	  i++;
	}
      else
	{
	  A[k] = sr[j];
	  j++;
	}
      cnt++;
    }

  free(sl);
  free(sr);
}





Measured memory_bytes: 5512
n = int(input())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return len(divisors)

count = 0
for i in range(1, n+1):
    if i % 2 == 1:
        if make_divisors(i) == 8:
            count += 1
print(count)

Measured memory_bytes: 38256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e16;
const ll mod = 1000000007;
#define rep(i, n) for (int i = 0; i < (ll)(n); i++)

int main() {
  string s, t; cin >> s >> t;
  ll res = 0;
  rep(i, s.size()) {
    if (s.at(i) != t.at(i)) res++;
  }
  cout << res << endl;
}

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

int main() {
    int N;
    cin >> N;
    vector<long> A(N), B(N), C(N);
    for (int i = 0; i < N; i++) {
        cin >> A.at(i);
    }
    for (int i = 0; i < N; i++) {
        cin >> B.at(i);
    }
    for (int i = 0; i < N; i++) {
        cin >> C.at(i);
    }

    long ans = 0;
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    sort(C.begin(), C.end());
    for (int i = 0; i < N; i++) {
        ans += (lower_bound(A.begin(), A.end(), B.at(i)) - A.begin()) * (C.end() - upper_bound(C.begin(), C.end(), B.at(i)));
    }

    cout << ans << endl;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
#define PI 3.14159265359
#define INF 1000100100000000000
#define MOD 1000000007
#define all(x) (x).begin(),(x).end()
typedef long long ll;
#define P pair<int, int>
#define PP pair<P,P>
#define T tuple<int,int,int> 
using namespace std;
 
int main(){
    int d; cin >> d;
    vector<int> c(26);
    rep(i,26) cin >> c[i];
    vector<vector<int> > s(d);
    rep(i,d)rep(j,26){
        int a; cin >> a;
        s[i].push_back(a);
    }
 
    //vector<int> ld(26,0);
    vector<vector<int> > ds(26);
    vector<int> days(d,1);

    
    //ll ans=0;
    rep(i,d){
        int t=days[i];
        ds[t].push_back(i);
        /*
        ld[t]=i+1;
        ans+=s[i][t];
        rep(j,26){
            ans-=c[j]*(i+1-ld[j]);
        }
        */
    }
 
    rep(i,100){
        rep(Q,26)rep(D,d){
        int pd=days[D];
        int be,af,be2,af2;
        int r,l;
        l=-1;
        r=ds[pd].size();
        while(l+1<r){
            int c=(l+r)/2;
            if(ds[pd][c]<=D) l=c;
            else r=c;
        }
        if(r==ds[pd].size()) af=d;
        else af=ds[pd][r];
        l=-1;
        r=ds[pd].size();
        while(l+1<r){
            int c=(l+r)/2;
            if(ds[pd][c]>=D) r=c;
            else l=c;
        }
        if(l==-1) be=-1;
        else be=ds[pd][l];

        int l2=-1;
        r=ds[Q].size();
        while(l2+1<r){
            int c=(l2+r)/2;
            if(ds[Q][c]<=D) l2=c;
            else r=c;
        }
        if(r==ds[Q].size()) af2=d;
        else af2=ds[Q][r];
        l2=-1;
        r=ds[Q].size();
        while(l2+1<r){
            int c=(l2+r)/2;
            if(ds[Q][c]>=D) r=c;
            else l2=c;
        }
        if(l2==-1) be2=-1;
        else be2=ds[Q][l2];

        if(c[Q]*(D-be2)*(af2-D)+s[D][Q]-c[pd]*(D-be)*(af-D)-s[D][pd]>0){
            days[D]=Q;
            ds[pd].erase(ds[pd].begin()+l+1);
            ds[Q].insert(ds[Q].begin()+l2+1,D);
        }
    }
    }
    //rep(i,d) cout << days[i] << endl;
    rep(i,d) cout << 4 << endl;
return 0;
}

Measured memory_bytes: 3740
import java.util.*;
public class Main{
  public static void main(String[]args){
    Scanner scan = new Scanner(System.in);
    String s = scan.next();
    String t = scan.next();
    int count = 0;
    for(int i=0;i<s.length();i++){
      if(s.charAt(i)!= t.charAt(i))
        count++;
    }
    System.out.println(count);
  }
}

Measured memory_bytes: 32152
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int INF = 1<<30;
int main(){
  int n, d;cin>>n>>d;
  vector<vector<double>> x(n, vector<double>(d));
  for(int i=0;i<n;i++){
  	for(int j=0;j<d;j++){
      cin>>x[i][j];
    }
  }
  int ans=0;
  for(int i=0;i<n;i++){
  	for(int j=0;j<i;j++){
      double dis=0;
      for(int k=0;k<d;k++){
      	dis += pow((x[i][k]-x[j][k]), 2);
      }
      dis = sqrt(dis);
      if(abs(dis-int(dis))<1e-6)ans++;
    }
  }
  cout<<ans<<endl;
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16
#define mod 1000000007

ll n;
double p[3000];
double dp[2][3001];

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

  cin>>n;
  rep(i,n)cin>>p[i];

  int crt=0,nxt=1;
  dp[0][0]=1.0;
  rep(i,n){
    rep(j,n+1)dp[nxt][j]=0;
    rep(j,n+1){
      dp[nxt][j+1]+=dp[crt][j]*p[i];
      dp[nxt][j]+=dp[crt][j]*(1.0-p[i]);
    }
    swap(crt,nxt);
  }
  double res=0;
  repl(i,(n+1)/2,n+1)res+=dp[crt][i];
  printf("%.10f\n", res);

  return 0;
}


Measured memory_bytes: 384
import java.io.*;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    String[] line1 = br.readLine().split(" ");
    int h = Integer.parseInt(line1[0]);
    int w = Integer.parseInt(line1[1]);
    
    char[][] c = new char[h][w];
    boolean[] viewLine = new boolean[h];
    boolean[] viewColumn = new boolean[w];
    
    for(int i=0; i<h; i++){
      c[i] = br.readLine().toCharArray();
    }
    for (int i=0; i<h; i++){
      for (int j=0; j<w; j++){
        if(c[i][j] == '#'){
          viewLine[i] = true;
          viewColumn[j] = true;
        }
      }
    }
    StringBuilder result =  new StringBuilder();
    for (int i=0; i<h; i++){
      if (!viewLine[i]) continue;
      for (int j=0; j<w; j++){
        if (viewColumn[j]) {
          result.append(c[i][j]);
        }
      }
      result.append("\n");
    }
    System.out.println(result.toString());
  }
}


Measured memory_bytes: 23124
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <stdio.h>
#include <string.h>
#include <cstdlib>
#include <math.h>
#include <bitset>
#include <iterator>
#include <iomanip>
#include <sstream>
#include <numeric>
#define INF INT_MAX
using namespace std;
int dx[5]={1,0,-1,0,0},dy[5]={0,1,0,-1,0};
long long gcd(long long a,long long b){if(a%b==0){return b;}else return gcd(b,a%b);}
long long lcm(long long a,long long b){if(a==0){return b;} return a/gcd(a,b)*b;}
long long MOD; template<class T> void mod(T n){MOD=n;}
#define sym cout<<"---------"<<endl;
#define ll long long
#define PL pair<long long, long long>
#define mk make_pair
#define en endl
#define WHITE 1
#define BLACK 2
#define GRAY 1
#define RE return 0
#define int ll
#define P pair<int,int>

int a[105],b[105];

signed main(){
  int n,m,x,y;
  cin>>n>>m>>x>>y;
  for(int i=0; i<n; i++) cin>>a[i];
  for(int i=0; i<m; i++) cin>>b[i];

  sort(a, a+n); sort(b, b+m);
  if(a[n-1]+1>b[0]){
    cout<<"War"<<en;
    RE;
  }

  for(int i=a[n-1]+1; i<=b[0]; i++){
    if(x<i&&i<=y){
      cout<<"No War"<<en;
      RE;
    }
  }
  cout<<"War"<<en;
}

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

int main(){
	long long x,k,d,n;
	cin>>x>>k>>d;
	
	n=abs(x/d);
	
	if(n>=k)x=abs(x)-k*d;
	else
		{   x=abs(x)-n*d;
			if((k-n)%2) 
			   x=x-d;
		}
	cout<<abs(x);
	return 0;
}

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

int book[10001];
vector<int> num;

int main()
{
	for (int i = 2; i <= 10000; ++i){
		if (!book[i]){
	 		num.push_back(i);
	 		for (int j = i; j <= 10000; j += i){
				book[j] = 1;
			}
		}
	}
	fill(book, book + 10001, 0);
	for (int i = 0; i < num.size(); ++i)
	{
		int sum = 0;
		for (int j = i; j < num.size(); ++j){
			if (sum + num[j] > 10000)break;
			else ++book[sum += num[j]];
		}
	}
	int n;
	while (cin >> n && n){
		cout << book[n] << endl;
	}
	return 0;
}


Measured memory_bytes: 3112
#include<bits/stdc++.h>
using namespace std;
#define  PI 3.14159265358979323846264338327950L           
                    
int main(){
    int a, b, h, m;
    scanf("%d%d%d%d", &a, &b, &h, &m);

    long double rad = PI * 2 * ((long double)h / 12.0 + ((long double)m / 60.0) / 12.0 - (long double)m / 60.0);

    long double rsq = (long double)(a * a + b * b) - (long double)(2 * a * b) * cos(rad);

    printf("%20.20Lf\n", sqrtl(rsq));

    return 0;
            
}

Measured memory_bytes: 4164
from collections import deque
H,W = map(int,input().split())
maze = []
dx = [1,0,-1,0]
dy = [0,1,0,-1]
for i in range(H):
    maze.append(list(input()))
def bfs(sx,sy):
    INF = -1
    cost = [[INF]*W for _ in range(H)]
    P = deque()
    P.append([sx,sy])
    cost[sx][sy] = 0
    while len(P) != 0:
        p = P.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "#" and cost[nx][ny] == INF:
                P.append([nx,ny])
                cost[nx][ny] = cost[p[0]][p[1]]+1
    return cost
def solve():
    ans = 0
    for i in range(H):
        for j in range(W):
            if maze[i][j] != "#":
                sx,sy = i,j
                cs = bfs(sx,sy)
                for k in range(len(cs)):
                    if max(cs[k]) > ans:
                        ans = max(cs[k])
    return ans
print(solve())

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

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

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);

    priority_queue<int> pq;
    for (int i = 0; i < n; i++) {
        int num;
        scanf("%d", &num);

        pq.push(num);
    }

    while (m > 0) {
        int cur = pq.top();
        pq.pop();

        m--;
        pq.push(cur / 2);
    }

    ll sum = 0;
    while (pq.size() > 0)
        sum += pq.top(), pq.pop();

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

    return 0;
}


Measured memory_bytes: 892
#include<cstdio>
int main(){
    int n,x;
    while(~scanf("%d%d",&n,&x)){
        int ans=1;
        int tot=0;
        int l;
        for(int i=0;i<n;i++){
            scanf("%d",&l);
            tot+=l;
            if(tot<=x) ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<cmath>
using namespace std;
int main(void){
	while( true ){
		int n;
		int x,y,z;
		
		cin >> x >> y >> z;
		if( x==0&&y==0&&z==0 ) break;
		cin >> n;

		for(int i = 0; i < n; i++){
			int r;
			
			cin >> r;
			if( sqrt((double)x*x+y*y) < 2*r ||
				sqrt((double)x*x+z*z) < 2*r ||
				sqrt((double)y*y+z*z) < 2*r ) cout << "OK\n";
			else cout << "NA\n";
		}
	}
	return 0;
}

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

#define FOR(i, j, k) for (int i = j; i < k; i++)
#define REP(i, j) FOR(i, 0, j)
#define fst first
#define snd second
#define pb push_back
#define eb emplace_back
#define all(obj) (obj).begin(), (obj).end()
#define rall(obj) (obj).rbegin(), (obj).rend()
typedef long long int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;

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;
}

template <typename T> istream &operator>>(istream &is, vector<T> &vec) {
  for (T &x : vec)
    is >> x;
  return is;
}

int main() {

  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout << fixed;

  int a, b;
  cin >> a >> b;

  if (a >= 13)
    cout << b << endl;
  else if (a >= 6)
    cout << b / 2 << endl;
  else
    cout << 0 << endl;

  return 0;
}


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

using namespace std;

int main()
{
   char s;
   cin >> s;

   if (isupper(s))
   {
       cout << "A" << endl;
   }
   else
   {
       cout << "a" << endl;
   }

   return 0;
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
#define mk make_pair
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;

int main(){
  string s;
  int n;
  while(cin>>s>>n){
    for(int i=0; i<s.size(); i+=n)
      cout<<s[i];
    cout<<endl;
  }
  return 0;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
using namespace std;
using Graph = vector<vector<int>>;
typedef pair<int,int> P;
typedef long long ll;

int main(){
    ll d; cin >> d;
    vector<ll> c(26); rep(i,26) cin >> c[i];
    vector<vector<ll>> g(d, vector<ll> (26));
    rep(i,d){
        rep(j,26){
            cin >> g[i][j];
        }
    }

    rep(i,d){
        cout << rand()%26 + 1 << endl;
    }
}

Measured memory_bytes: 3708
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A,B,sum;
  cin >> A >> B;
  sum = 0;
  for (int i = A; i < B+1; i++){
    if ((i/10000)==(i%10) && ((i/1000)%10)==((i/10)%10))
      sum++;
  }
  cout << sum << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#define U 1
#define D 2
#define R 3
#define L 4
#define MAX 100

int main(void){
    int dx[L+1] = {0,0,0,1,-1};
    int dy[L+1] = {0,-1,1,0,0};
    int pnl[MAX][MAX];
    int visited[MAX][MAX];
    char buf[MAX+1];
    int h,w,x,y,dir;
    
    while (scanf("%d %d",&h, &w)){
        if (h==0 && w==0) break;
        // load
        for (int i=0; i<h; i++){
            scanf("%s", buf);
            for (int j=0; j<w; j++){
                visited[j][i] = pnl[j][i] = 0;
                switch (buf[j]){
                    case '^' : pnl[j][i]=U; break;
                    case 'v' : pnl[j][i]=D; break;
                    case '>' : pnl[j][i]=R; break;
                    case '<' : pnl[j][i]=L; break;
                }
            }
        }
        // move
        x = y = 0;
        while(pnl[x][y] && !visited[x][y]){
            visited[x][y]=1;
            dir = pnl[x][y];
            x += dx[dir];
            y += dy[dir];
        }
        if (pnl[x][y]){
            printf("LOOP\n");
        } else {
            printf("%d %d\n", x,y);
        }
    }
    
    return 0;
}

Measured memory_bytes: 1120
#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#include<utility>
#include<queue>
#include<vector>
#include<stack>
#include<sstream>
#include<algorithm>
#define forn(i,a,b)for(int i=(a),_b=(b);i<=_b;i++)
#define fore(i,b,a)for(int i=(b),_a=(a);i>=_a;i--)
#define rep(i,n)for(int i=0,_n=n;i<n;i++)
#define ll long long
#define pii pair<int,int>
#define vi vector<int>
#define vpii vector<pii>
#define m_p make_pair
#define re return
#define pb push_back
#define si set<int>
#define ld long double
#define X first
#define Y second
#define st string
#define ull unsigned long long
#define mod 1000000007
#define INF 1000000007
#define x1 XZVJDFADSPFOE
#define y1 GASDIJSLDAEJF
#define x2 DFDAJKVOHKWIW
#define y2 PSFSAODSXVNMQ
#define LLINF 0x3f3f3f3f3f3f3f3fLL
using namespace std;
inline void read(int &x)
{
	short negative=1;
    x=0;
    char c=getchar();
    while(c<'0' || c>'9')
    {
		if(c=='-')
			negative=-1;
		c=getchar();
	}
    while(c>='0' && c<='9')
        x=(x<<3)+(x<<1)+(c^48),c=getchar();
    x*=negative;
}
ll quickpower(ll n,ll k){
	ll ans=1;
	while(k){
		if(k%2){
			ans*=n;
			ans%=mod;
		}
		n*=n;
		n%=mod;
		k/=2;
	}
	return ans;
}
int main()
{
	ios::sync_with_stdio(0);
	//think twice,code once
	int x,n;
	int a[11111];
	cin>>x>>n;
	rep(i,n)cin>>a[i];
	rep(i,n)x-=a[i];
	x=max(x,-1);
	cout<<x<<endl;
	return 0;
}



Measured memory_bytes: 3664
#include<bits/stdc++.h>
using namespace std;
int arr[120];
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;++i)
    {
        cin>>arr[i];
    }
    sort(arr,arr+n);
    int l=arr[0],r=arr[n-1];
    int mi=100000000;
    for(int i=l;i<=r;++i)
    {
        int mid=i;
        int temp=0;
        for(int i=0;i<n;++i)
        {
            temp+=(arr[i]-mid)*(arr[i]-mid);
        }
        mi=min(mi,temp);
    }
    cout<<mi<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<algorithm>
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<stack>
#include<cmath>
#include<list>
#include<set>
#include<map>

using namespace std;
long long MOD = 1000000007LL;
const double PI = 3.14159265358979323846;
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483648
#define INT_MAX 2147483647
#define endl "\n"

int main() {
	string s, t;
	cin >> s >> t;
	int mCount = INT_MAX;
	for (int j = 0; j <= s.length() - t.length(); ++j) {
		int count = 0;
		for (int i = 0; i < t.length(); ++i) {
			if (s[j + i] != t[i])++count;
		}
		mCount = min(mCount, count);
	}

	cout << mCount << endl;
	return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
/////////////////////////////////
int main(){
    int n;
    cin>>n;
    vector<ll> a(n),b(n);
    rep(i, n) cin >> a[i];
    b[n - 1] = a[n - 1];
    for (int i = n - 1; i >= 1;i--){
        b[i - 1] = (b[i] + a[i - 1])%1000000007;
    }
    ll ans = 0;
    rep(i,n-1){
        ans = (ans + a[i] * b[i + 1]) % 1000000007;
    }
    cout << ans << endl;
}

Measured memory_bytes: 6352
#include<stdio.h>
#define N 100


int main(){
  int n,A[N+1],k;
  int i;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
  for(k=0;k<n;k++){
    if(k>0)printf(" ");
    printf("%d",A[k]);
  }
  printf("\n");

int j,v;
for(i=1;i<n;i++){
  v=A[i];
  j=i-1;
  while(j>=0 && A[j]>v){
    A[j+1]=A[j];
    j--;
    A[j+1]=v;
  }
  for(k=0;k<n;k++){
    if(k>0)printf(" ");
    printf("%d",A[k]);
  }
  printf("\n");
 }
return 0;
}

Measured memory_bytes: 1768
#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main(int argc, char *argv[]){
	int N, A, B;
	string s;
	cin >> N;
	cin >> A;
	cin >> B;
	cin >> s;

	int passCount = 0, passCountB = 0;
	for (int i = 0; i < N; i++) {
		switch(s[i]) {
			case 'a':
				if (passCount < A + B) {
					cout << "Yes\n";
					passCount ++;
				}
				else 
					cout << "No\n";
				break;
			case 'b':
				if (passCount < A + B && passCountB < B) {
					cout << "Yes\n";
					passCount ++;
					passCountB ++;
				}
				else 
					cout << "No\n";
				break;
			case 'c':
				cout << "No\n";
				break;
		}
	}
}


Measured memory_bytes: 896
def inpf() a=gets.chomp.split(" ").map(&:to_f)end

def inps() a=gets.chomp.split(" ")end

def copy(a) Marshal.load(Marshal.dump(a)) end

def kaijo(n,r = 10**9+7)(n < 2)? 1 : (2..n).inject{|memo,u|memo=(memo*u)%r} end

def na(n,d=0) Array.new(n,d)end

def na2(n,m,d=0) Array.new(n){Array.new(m,d)}end

def na3(n,m,l,d=0) Array.new(n){Array.new(m){Array.new(l,d)}}end

def inp() a=gets.chomp.split(" ").map(&:to_i)end

def r_up(a, b) (a+b-1)/b end

def sum(a) a.inject(:+) end

n,k = inp
s = gets.chomp
mae = s[0]
ans = 0
f = false
nn = s.size
a = (1...nn).to_a
a.each do |i|
  if(mae != s[i])
    if(0 < k)
      ans += 1
      k -= 1 if(f)
      f = !f
    end
  else
    ans += 1
  end
  mae = s[i]
end
p ans

Measured memory_bytes: 2812
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

const double EPS = 1e-8;

int dcmp(double d) {
    if (fabs(d) < EPS) {
        return 0;
    }
    else {
        return d < 0? -1 : 1;
    }
}

struct Vector {
    double x, y;
    Vector(double x = 0, double  y = 0):x(x), y(y) {
    }
    
    bool operator< (const Vector& other) const {
        return dcmp(y - other.y) != 0? y < other.y : dcmp(x - other.x) < 0;
    }
};

typedef Vector Point;

struct PointCmp {
    bool operator()(const Point& a, const Point& b) {
        return (dcmp(a.y - b.y) < 0 || 
                (dcmp(a.y - b.y) == 0 && dcmp(a.x - b.x) < 0));
    }
};

//struct PointCmp1 {
//    bool operator()(const Point& a, const Point &b) {
//        return (dcmp(a.x - b.x) < 0 || 
//                (dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) < 0));
//    }
//};

Vector operator-(const Vector& a, const Vector& b) {
    return Vector(a.x - b.x, a.y - b.y);
}

double cross(const Vector& a, const Vector& b) {
    return a.x * b.y - a.y * b.x;
}

double ccw(const Point& a, const Point& b, const Point& c) {
    return cross(b - a, c - a);
}

vector<Point> convexHull(vector<Point>& p) {
    int n = p.size();
    sort(p.begin(), p.end());   
    vector<Point> ch(n + 1);
    
    int m = 0;
    for (int i = 0; i < n; i++) {
        while (m > 1 && dcmp(ccw(ch[m - 2], ch[m - 1], p[i])) < 0) {
            m--;
        }
        ch[m++] = p[i];
    }
    int k = m;
    for (int i = n - 2; i >= 0; i--) {
        while (m > k && dcmp(ccw(ch[m - 2], ch[m - 1], p[i])) < 0) {
            m--;
        }
        ch[m++] = p[i];
    }
    
    if (n > 1) {
        m--;
    }
    ch.resize(m);
    
    return ch;
}

int main() {
    int n; 
    cin >> n;
    vector<Point> p(n);
    
    for (int i = 0; i < n; i++) {
        cin >> p[i].x >> p[i].y;
    }
   
    vector<Point> ch = convexHull(p);
    
    int m = ch.size();
    
    cout << m << endl;
    
    for (int i = 0; i < m; i++) {
        cout << ch[i].x << " " << ch[i].y << endl;
    }
    
    return 0;
}

Measured memory_bytes: 6028
#include<stdio.h>
#include<math.h>
#include<string.h>
int main(){
    int K,S;
    scanf("%d %d",&K,&S);
    int ans=0;
    for(int i=0;i<=K && i<=S;i++){
        for(int j=0;j<=K && i+j<=S;j++){
            if(S-i-j>=0 && S-i-j<=K) ans++;
        }
    }
    printf("%d",ans);
}


Measured memory_bytes: 128
import sys
n = int(input())
a = list(map(int, input().split()))

p = 'APPROVED'
for i in a:
  if i % 2 == 0:
    if i % 3 == 0 or i % 5 == 0:
      continue
    else:
      print('DENIED')
      sys.exit()
print(p)

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

int main()
{
  int N, M, C, B[10], t, sum, ans = 0;
  
  cin >> N >> M >> C;
  
  for (int i = 0; i < M; i++) {
    cin >> B[i];
  }
  
  for (int i = 0; i < N; i++) {
    sum = 0;
    
    for (int j = 0; j < M; j++) {
      cin >> t;
      sum += t * B[j];
    }
    
    if (sum + C > 0) {
      ans++;
    }
  }
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int h[n];
    for(int i = 0;i < n;i++) {
        cin >> h[i];
    }

    int max = h[0];
    int sam = 1;
    for(int i = 1;i < n;i++) {
        if(max<=h[i]) {
            sam++;
            max = h[i];
        }
    }
    cout << sam << endl;

}

Measured memory_bytes: 256