akhauriyash/Code-Regression huggingface dataset:
N, L = map(int, input().split())
if L >= 0:
  l = map ( lambda x : x + L, range(1, N))
  print(sum(l))
elif -L < N :
  l = map ( lambda x : x + L, range(0, N))
  print(sum(l))
else:
  l = map ( lambda x : x + L, range(0, N))
  print(sum(l) - (N+L-1))

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

using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()

template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;

template <typename T>
struct BIT {
  vector<T> bit;
  // 単位元, 要素数以下の最大の2べき
  int neutral = 0, n;
  // 更新クエリ, 区間クエリ
  function<T(T,T)> f = [](const T l, const T r) { return l+r; },
    g = [](const T l, const T r) { return l+r; };

  BIT(int n_ = 1e5) { init(n_); }
  void init(int n_) {
    bit.assign(n_+1, neutral);
    n=1; while(n*2 < n_+1) n*=2;
  }
  void update(int i, T w) {
    for(int x = i+1; x < bit.size(); x += x&-x) bit[x] = g(bit[x], w);
  }
  // [0,i]
  T query(int i) {
    T ret = neutral;
    for(int x = i+1; x > 0; x -= x & -x) ret = f(ret, bit[x]);
    return ret;
  }
  // 合計がw以上の最小の位置 ToDo:verify
  int lower_bound(T w) {
    if(w <= 0) return 0;
    int idx = 0;
    for(int i=n; i>0; i>>=1) {
      if(idx+i < bit.size() && bit[idx+i] <= w) {
        w -= bit[idx+i];
        idx += i;
      }
    }
    return idx;
  }
};

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

  string s;
  cin >> s;
  int n = s.size();

  ll ret = 0, tmp = 0;
  REP(i, n) {
    if(s[i] == 'B') {
      tmp++;
    } else {
      ret += tmp;
    }
  }
  cout << ret << endl;

  return 0;
}


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

#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define FOR(e, c) for (auto &e : c)
#define SORT(v, n) sort(v, v + n);
#define vsort(v) sort(v.begin(), v.end());
#define rvisort(v) sort(v.begin(), v.end(), greater<int>());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
// #define int long long
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using ul = unsigned long;

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

int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
int LCM(int a, int b) { return a * b / GCD(a, b); }

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

inline bool inside(int y, int x, int H, int W) {
    return (y >= 0 && x >= 0 && y < H && x < W);
}

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

signed main()
{
  ll n,k; cin>>n>>k;
  vll x(n);
  rep(i,n) cin>>x[i];
  
  ll centor=n-1;
  rep(i,n) {
    if(x[i]>=0){
      centor=i;
      break;
    }
  }
  
  ll ans =LINF;
  for(ll i=max(0LL,centor-k); i+k-1<n&&i<=centor; i++){
    ll tmp;
    if(i==centor-k || i-centor+1==k) {
      tmp=abs(x[i]);
    }
    else {
      tmp=abs(x[i+k-1]-x[i])+min(abs(x[i]),abs(x[i+k-1]));
    }
    chmin(ans,tmp);
  }
  cout<<ans<<endl;
  
}


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


int main(){
  vector<char> a(6);
  for(int i=0;i<6;i++){
    cin >> a.at(i);
  }
  if(a.at(0)==a.at(5)&& a.at(1)==a.at(4)&&a.at(2)==a.at(3)){
    cout <<"YES"<<endl;
  }
  else{
    cout <<"NO"<<endl;
  }
  }


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
char a[16], b[16] = {'C', 'O', 'D', 'E', 'F', 'E', 'S', 'T', 'I', 'V', 'A', 'L', '2', '0', '1', '6'};
int ans=0;
int main(){
    cin >> a;
    for(int i = 0; i < 16; i ++){
        if(a[i] != b[i]) ans ++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define rep1(i,n) for(int i=1;i<=(int)n;i++)
#define sp(n) cout << fixed << setprecision(n)
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; }
typedef long long ll;
using namespace std;
int main(void){
    ll n,k;cin>>n>>k;
    vector<ll> a(n),f(n);
    rep(i,n) cin>>a[i];
    rep(i,n) cin>>f[i];
    sort(a.begin(),a.end());
    sort(f.rbegin(),f.rend());
    ll right=1e+18,left=-1;
    while(right-left>1){
        ll mid=(right+left)/2;
        ll tot=0;
        rep(i,n){
            ll buf=a[i]*f[i];
            buf-=mid;
            tot+=max((buf+f[i]-1)/f[i],(ll)0);
        }
        //cout<<mid<<" "<<tot<<endl;
        if(tot>k)left=mid;
        else right=mid;
    }
    cout<<right<<endl;
}

Measured memory_bytes: 3328
#include "bits/stdc++.h"
#define ll long long
#define mk make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
using namespace std;
const int MAXN=1e5+9;
map<ll,int> mp;
const ll INF=2e18;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	for(ll i=1;i<=10000;i++)
	{
		ll res=1;
		for(int j=1;j<=5;j++)
		{
			res=res*i;
		}
		if(res>INF)
		{
			break;
		}
		mp[res]=i;
	}
	ll x;
	cin>>x;
	for(ll i=0;i<=10000;i++)
	{
		ll res=1;
		for(int j=1;j<=5;j++)
		{
			res=res*i;
		}
		if(mp.find(x-res)!=mp.end())
		{
			cout<<mp[x-res]<<" "<<(-i)<<endl;
			return 0;
		}
		if(mp.find(x+res)!=mp.end())
		{
			cout<<mp[x+res]<<" "<<i<<endl;
			return 0;
		}
	}
	assert(false);
	return 0;
}

Measured memory_bytes: 3948
#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#include<iomanip>
#include<cstring>
#include<string>
#include<vector>
#include<math.h>
#include<queue>
#include<map>
using namespace std;
#define ll long long
const int INF=0x3f3f3f3f;
int mode=1e9+7;
int main()
{
	string s,t;
	cin>>s>>t;
	int a,b;
	cin>>a>>b;
	string u;
	cin>>u;
	if(s==u)
	{
		a-=1;
	 } 
	 else if(t==u)
	 {
	 	b-=1;
	 }
	 cout<<a<<" "<<b<<endl;
	 return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define inf 1e18
#define mk make_pair
#define ld long double
#define mod 1000000007
#define fi first
#define se second
#define fastIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define test ll t; cin>>t; while(t--)
ll power(ll a,ll n)
{
    ll p;
    if(n==0)
    {
        return 1;
    }
    p=power(a,n/2);
    p=p*p;
    if(n%2==1)
    {
        p=p*a;
    }
    return p;
}
int main()
{
    ll h,n;
    cin>>h>>n;
    ll sum=0,a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        sum+=a[i];
    }
    if(h>sum)
    {
        cout<<"No\n";
    }
    else
    {
        cout<<"Yes\n";
    }
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <stdlib.h>
#include <vector>

using namespace std;
struct Node {
    int key;
    Node *next, *prev;
};
static string INSERT = "insert";
static string DELETE = "delete";
static string DELETE_FIRST = "deleteFirst";
static string DELETE_LAST = "deleteLast";

Node* nil;
void print()
{
    Node* n = nil->next;
    while (n != nil) {
        cout << n->key;
        n = n->next;
        if (n != nil) {
            cout << " ";
        }
    }
    cout << endl;
}

void init()
{
    nil = (Node*)malloc(sizeof(Node));
    nil->next = nil;
    nil->prev = nil;
}

void insertN(int key)
{
    Node* n = (Node*)malloc(sizeof(Node));
    n->key = key;
    n->next = nil->next;
    n->prev = nil;
    nil->next->prev = n;
    nil->next = n;
}
void deleteN(int key)
{
    Node* n = nil->next;
    while (n != nil) {
        if (key == n->key) {
            n->prev->next = n->next;
            n->next->prev = n->prev;
            free(n);
            break;
        }
        n = n->next;
    }
}
void deleteLastN()
{
    Node* n = nil->prev;
    n->prev->next = nil;
    nil->prev = n->prev;
    free(n);
}
void deleteFirstN()
{
    Node* n = nil->next;
    n->next->prev = nil;
    nil->next = n->next;
    free(n);
}

int main()
{
    init();
    int N = 0;
    scanf("%d", &N);
    char command[20];
    int key = 0;
    for (int i = 0; i < N; i++) {
        cin >> command;
        if (INSERT == command) {
            cin >> key;
            insertN(key);
        } else if (DELETE == command) {
            cin >> key;
            deleteN(key);
        } else if (DELETE_FIRST == command) {
            deleteFirstN();
        } else if (DELETE_LAST == command) {
            deleteLastN();
        }
    }
      print();
    return 0;
}

Measured memory_bytes: 34468
#include <stdio.h>

int main(void){
    int a,b,ans=0;
    scanf("%d %d",&a,&b);
    if(a<2)ans=0;
    if(b<2)ans+=0;
    if(a>=2)ans+=a*(a-1)/2;
    if(b>=2)ans+=b*(b-1)/2;
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 128
def edit_distance():
 s = raw_input()
 t = raw_input()
 a = len(s)
 b = len(t)
 x = [0 for i in range(b+1)]
 for i in range(a):
   q = s[i]
   x2 = x+[]
   for j in range(b):
    if (q ==t[j]):
     x[j+1] =x2[j]+1
    elif (x[j+1]<x[j]):
     x[j+1] =x[j]
 return x[-1]

n = input()
for i2 in range(n):
 print edit_distance()

Measured memory_bytes: 6484
#include <iostream>
#include <vector>
#include <cstdlib>  
#include <algorithm>
#include <string>

using namespace std;
 
int main() {
    long n,max,sa;
    cin >> n;
    sa = n;
    max = 1;
    long jougen = n;
    if(n > 1000000) jougen =1000000;
    for(long i=1;i<=jougen;i++){
      if(n%i==0){
          long aho = n/i;
          long sasa = abs(aho-i);
          if(sasa <= sa) {
            sa = sasa;
            max = i;
          }
      }
    }
    long k = n/max;
    cout<<k+max-2;
    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);

		int l = sc.nextInt();
		int r = sc.nextInt();
		int d = sc.nextInt();

		int ans = 0;

		for (int i=l; i<=r; i++){
			if (i % d == 0){
				ans++;
			}
		}
		System.out.println(ans);
	}

}

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

int main(){
    int a,b,c,buf;
    
    cin >> a >> b >> c;
    
    if(a>b){
        buf = a;
        a = b;
        b = buf;
    }
    
    if(b>c){
        buf = b;
        b = c;
        c = buf;
    }
    
    if(a>b){
        buf = a;
        a = b;
        b = buf;
    }
    
    cout << a << " " << b << " " << c << endl;
    
    return 0;
}


Measured memory_bytes: 3100
line=input().split(" ")
a=int(line[0])
b=int(line[1])
c=int(line[2])
d=int(line[3])
 
while a>0 and c>0:
  c=c-b
  if c<=0:
    print("Yes")
    break
  a=a-d
  if a<=0:
    print("No")
    break

Measured memory_bytes: 9188
// warm heart, wagging tail,and a smile just for you!
//
//                            ▒█████▒▒
//                             ██████████▒
//                             ▒████████████▒
//                            ██████████████████
//                           ████████████████████▒
//                          ▒██████████████████████▒
//                          ▒███████████████████████
//                      ▒████▒▒▒▒▒▒█████████████████▒
//                    ███▒▒▒▒▒▒██████████████████████▒▒▒
//                  ▒██▒▒███████████████████████▒▒▒▒▒██████
//                 ▒█████████████████████████▒▒▒▒▒▒█████████▒
//                 ▒█████████████████████▒▒▒▒▒▒██████████████
//                  ▒████         ████▒▒▒▒▒████         ████▒
//              ▒█████▒    ████    ▒▒▒▒███████    ████    ██████▒
//            ▒██▒▒▒▒▒    ██████    █████████    ██████    ██▒▒▒██▒
//           █████████   ████████   █████████   ████████   ▒▒▒▒█████
//          ▒█████████    ██████    ████████▒    ██████    █████████
//          ▒██████████    ████    █████▒▒▒▒▒▒    ████    ██████████
//           ████████████        ▒▒▒▒▒▒▒████████        ███████████▒
//       ▒██████████▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒███████████████████████████████████▒
//     ███▒▒▒▒▒▒▒▒▒▒▒▒█████████████████████████████████████████▒▒████████▒
//   ▒▒▒▒▒▒▒▒▒██████████████                         ███████▒▒▒▒███████████
//   █████████████████████████                     ███████▒▒▒██████████████▒
//   █████████████████████████████             ███████▒▒▒██████████████████▒
//   ██████████████████████████████████████████████████████████████████████
//    ██████████████████████████████████████████████████████████████████▒
//      ▒█████████████████▒▒▒▒▒▒▒██████████████████████████████████▒▒▒
//
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
const double EPS = 1e-9;
#define INF (1LL<<60)
#define D double
#define fs first
#define sc second
#define int long long
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for(int i = (b-1);i>=(a);--i)
#define REP(i,n)  FOR(i,0,(n))
#define RREP(i,n) RFOR(i,0,(n))
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x)  cout << #x << " = " << (x) << endl;
#define SP << " " << 
typedef pair<int,int> P;
typedef vector<int> vec;
typedef vector<vector<int>> mat;

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

  int h,w,n;
  cin >> h >> w >> n;

  vector<int> a(n);
  REP(i,n) cin >> a[i];
  
  int now = 0;
  mat ans(h,vec(w));
  REP(i,h){
    if(i%2==0){
      REP(j,w){
        ans[i][j] = now;
        a[now]--;
        if(a[now]==0) now++;
      }
    }
    else{
      RREP(j,w){
        ans[i][j] = now;
        a[now]--;
        if(a[now]==0) now++;
      }      
    }
  }

  REP(i,h){
    REP(j,w) cout << ans[i][j]+1 << " ";
    cout << endl;
  }

  return 0;
}

Measured memory_bytes: 512
N = int(input())
A = list(map(int,input().split()))
m = 0
for i in range(N):
    if A[i] < 0:
        m += 1
Ap = list(map(abs,A))
Ap.sort()
if m %2 == 1:
    ans = sum(Ap) - 2*Ap[0]
else:
    ans = sum(Ap)
print(ans)

Measured memory_bytes: 14332
h, w = map(int, input().split(" "))
ss = [list(input()) for i in range(h)]

def hb(i, j):
    b = ss[i][j] == '#'
    if j > 0:
        b += ss[i][j-1] == '#'
    if j < w - 1:
        b += ss[i][j+1] == '#'
    return b

for i in range(h):
    for j in range(w):
        if ss[i][j] == '#':
            continue

        b = 0
        if i > 0:
            b += hb(i-1, j)
        b += hb(i, j)
        if i < h - 1:
            b += hb(i+1, j)
        ss[i][j] = chr(ord('0') + b)
print('\n'.join(''.join(s) for s in ss))


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

using namespace std;
using ull = unsigned long long;
using ll = long long;
using lli = long long int;
using ld = long double;
using pa = pair<int, int>;
using ppa = pair<pa, int>;
#define SORT(v, n) sort(v, v + n);
#define ALL(v) v.begin(), v.end()
#define VSORT(v) sort(ALL(v))
#define GRESORT(v) sort(ALL(v), greater<ll>())
#define REVERSE(v) reverse(ALL(v))
#define overlap(v) v.erase(unique(ALL(v)), v.end())
#define debug(x) cout << #x << ": " << x << endl
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, n) FOR(i, 0, n)
#define RFOR(i, a, b) for (int i = (b - 1); i >= a; i--)
#define rrep(i, n) RFOR(i, 0, n)
#define INF INT_MAX
#define SUP INT_MIN
#define mins(a, b) a = min(a, b)
#define maxs(a, b) a = max(a, b)

// 4近傍
// int dy[]={0, 1, 0, -1};
// int dx[]={1, 0, -1, 0};

// 8近傍
// int dy[]={0,0,1,-1,1,1,-1,-1};
// int dx[]={1,-1,0,0,1,-1,1,-1};

// const ll MOD = 1000000007;

ll pow_mod(ll a, ll b, ll mod) {
    ll tmp = 1;
    a %= mod;
    if (b > 0) {
        tmp = pow_mod(a, b / 2, mod);
        if (b % 2)
            tmp = (((tmp * tmp) % mod) * a) % mod;
        else
            tmp = (tmp * tmp) % mod;
    }
    return tmp;
}

ll gcd(ll x,ll y){
    if(x == 0) return y;
    return gcd(y%x,x);
}

void solve(){
    string s;
    cin >> s;
    for(int i = 0; i < s.size(); i++){
        if(i != 5 && i != 13) cout << s[i];
        else cout << " ";
    }
    cout << endl;
}

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

    solve();

    return 0;
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))

ope = 0
for i in range(n):
    if b[i] > a[i]:
        ope+=(b[i]-a[i]+1)//2

if sum(b) - sum(a) < 0:
    print('No')        
elif ope <= sum(b) - sum(a):
    print('Yes')
else:
    print('No')

Measured memory_bytes: 40432
from collections import defaultdict
N, M = map(int,input().split())
S = input()
T = input()

def gcd(a, b):
    if b > a:
        a, b = b, a

    if a % b == 0:
        return b

    return gcd(b, a % b)

def lcm(a, b):
    return a * b // gcd(a, b)

len_l = lcm(N, M)
dict = defaultdict(str)

for i, s in enumerate(S):
    dict[i * len_l//N] = s

for j, t in enumerate(T):
    if dict[j * len_l//M] != "" and dict[j * len_l//M] != t:
        print(-1)
        exit()

print(len_l)

Measured memory_bytes: 15652
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr ll mod=1000000007;
constexpr ll mod998=998244353;

int N;
ll A[200000],B[200000],res;
map<pair<ll,ll>,ll>mp;

ll pw(ll x,ll y){
	ll a=1;
	while(y){
		if(y&1){
			a=a*x%mod;
		}
		x=x*x%mod;
		y/=2;
	}
	return a;
}

ll gcd(ll x,ll y){
	if(y)return gcd(y,x%y);
	else return x;
}


int main(){
	cin>>N;
	for(int i=0;i<N;i++){
		cin>>A[i]>>B[i];
		if(A[i]<0){
			A[i]=-A[i];
			B[i]=-B[i];
		}
		if(A[i]==0&&B[i]==0)res++;
		else {
			if(A[i]==0)B[i]=1;
			if(B[i]==0)A[i]=1;
			ll g=gcd(A[i],abs(B[i]));
			A[i]/=g;
			B[i]/=g;
			mp[{A[i],B[i]}]++;
		}
	}
	ll c=1;
	for(int i=0;i<N;i++){
		if(B[i]>0){
			c*=pw(2,mp[{A[i],B[i]}])+pw(2,mp[{B[i],-A[i]}])-1;
			c%=mod;
			mp[{A[i],B[i]}]=mp[{B[i],-A[i]}]=0;
		}
		else{
			c*=pw(2,mp[{A[i],B[i]}])+pw(2,mp[{-B[i],A[i]}])-1;
			c%=mod;
			mp[{A[i],B[i]}]=mp[{-B[i],A[i]}]=0;	
		}
	}
	c+=mod-1;
	res+=c;
	res%=mod;
	cout<<res<<endl;
}


Measured memory_bytes: 31516
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+7;
const int mod =2019;
char a[maxn];
int b[maxn],c[2020];
int  Pow(int a,int b)
{
	 int res=1;
	 while(b){
	  if(b&1)  res=res*a%mod;
	  a=a*a%mod;
	  b>>=1;
	 }
	 return res%mod;
}
int main()
{
	scanf("%s",a+1);
	int n=strlen(a+1);
	for(int i=1;i<=n;i++)
	{
	b[i]=(mod+b[i-1]+(a[i]-'0')*Pow(10,(n-i))%mod)%mod;
	c[b[i]]++;
	} 
   long long sum=0;
   for(int i=0;i<2019;i++)
   	sum+=1ll*c[i]*(c[i]-1)/2;
   if(c[0]) cout<<sum+c[0]<<endl;
   else cout<<sum<<endl;	
	
}

Measured memory_bytes: 4676
/* 
   AOJ 2508
   King's Inspection
   2015/7/25
*/
#include<stdio.h>


#define K_MAX 100
#define L_MAX 200
#define LARGE_MIN 65
#define LARGE_MAX 90
#define SMALL_MIN 97
#define SMALL_MAX 122
#define ALPHABET_RANGE 26

void ans_f(int* key, int key_num, int* list, int list_num, char* out_str)
{
  int i, new_char, key_val, j;

  for(i = 0; i <= list_num; i++)
    {
      /* printf("\n"); */
      /* printf("%c", list[i]); */
      key_val = key[i % key_num];
      new_char = list[i] - key_val;
      if(list[i] <= LARGE_MAX)
	{
	  //	  printf("hoge");
	  if(LARGE_MIN <= new_char)
	    {
	      list[i] = new_char;
	      //	      printf("0");
	    }
	  else
	    {
	      if(LARGE_MIN - ALPHABET_RANGE <= new_char)
		{
		  list[i] = SMALL_MAX - (LARGE_MIN - new_char) + 1;
		  //  printf("1");
		}
	      else
		{
		  list[i] = ALPHABET_RANGE * 2 - key_val + list[i];
		  //		  printf("2");
		}
	    }
	}
      else
	{
	  if(SMALL_MIN <= new_char)
	    {
	      list[i] = new_char;
	      //	      printf("3");
	    }
	  else
	    {
	      if(LARGE_MIN + 6 <= new_char && LARGE_MAX + 6)
		{
		  list[i] = new_char - 6;
		  //  printf("4");
		}
	      else
		{
		  list[i] = ALPHABET_RANGE * 2 - key_val + list[i];
		  //		  printf("5");
		}
	    }
	}
    }
  for(j = 0; j < i; j++)
    {
      out_str[j] = (char)list[j];
    }
  out_str[j] = '\n';
  out_str[j + 1] = '\0';
}

int main(void)
{
  int key_num, i, number = 0;
  int key[K_MAX], list[L_MAX];
  char input_char, ans_str[L_MAX], dast;
  while(1)
    {
      for(i = 0; i < K_MAX; i++)
	{
	  key[i] = 0;
	}
      for(i = 0; i < L_MAX; i++)
	{
	  list[i] = 0;
	}

      scanf("%d", &key_num);

      if(key_num == 0)
	{
	  break;
	}

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

      scanf("%c", &dast);
      //      scanf("%c", &dast);
      for(i = 0; ; i++)
	{
	  //	  printf("fuga");
	  scanf("%c", &input_char);
	  if(input_char == '\n')
	    {
	      break;
	    }
	  list[i] = (int)input_char;
	}
      //      printf("foo");
      ans_f(key, key_num, list, i - 1, ans_str);
 
      printf("%s", ans_str);

    }
  return 0;
}

Measured memory_bytes: 600
#include<iostream>
#include<math.h>
#include<stdlib.h>
#include<string>
#include<vector>
#include<map>
#include<algorithm>

using namespace std;

#define INF (1<<30)

int n;
int a[100001];
int dp[100001][2];

int dpsolve(){
	random_shuffle(a, a+n);
	fill_n(*dp,100001*2,-1);
	for(int d = n-1;d != -1;d--){
		for(int skip = 0;skip < 2;skip++){
			if(d == n-1){
				// if(skip==0){//まだ何も飛ばしてない
				// 	return a[d];
				// }else{
				// 	return a[d];
				// }
				dp[d][skip] = a[d];
				continue;
			}
			int ans = 0;
			ans = max(ans, __gcd(dp[d+1][skip], a[d]));//選ぶ
			if(skip == 0){
				ans = max(ans, dp[d+1][1]);//スキップする
			}
			dp[d][skip] = ans;
		}
	}
	return dp[0][0];
}

int main(){
	cin >> n;
	for(int i = 0;i < n;i++){
		cin >> a[i];
	}
	int ans = 0;
	for(int i = 0;i < 5;i++){
		ans = max(ans, dpsolve());
	}
	cout << ans << endl;
}

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

#define lf double
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);
    int n, k; cin>>n>>k;
    string s; cin>>s;
    int ans = n-1;
    rep(i, s.size()-1){
        if (s[i]!=s[i+1]) ans--;
    }
    ans += k*2;
    ans = min(ans, n-1);
    cout << ans << "\n";
	return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long
using namespace std;
int dp[3010][3010];
string a, b, ans;
int f(int i, int j){
    if(i == a.size() || j == b.size()) return 0;
    int &ans = dp[i][j];
    if(dp[i][j] == -1){
        if(a[i] == b[j]) ans = max(ans, f(i + 1, j + 1) + 1);
        else ans = max(f(i + 1, j), f(i, j + 1));
    }
    return ans;
}
void build(int i,int j){
    if(i == a.size() || j == b.size())return;
    ll answer = f(i, j);
    if(a[i] == b[j] && answer == f(i + 1, j + 1) + 1){
        ans.push_back(a[i]);
        build(i + 1, j + 1);
    }
    else if(answer == f(i + 1, j))build(i + 1, j);
    else if(answer == f(i, j + 1))build(i, j + 1);
    return;
}
int main(){
    fast;
    cin >> a >> b;
    memset(dp, -1, sizeof dp);
    ans.clear();
    f(0, 0);
    build(0, 0);
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 39212
#define __USE_MINGW_ANSI_STDIO 0
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <string.h>
#include <math.h>

using namespace std;

#define PI 3.141592653589793
#define epsilon 0.000000001
#define INF 1000000000000000000
#define MOD 1000000007

int N, neededSum [1010], black [1010];
vector<int> children [1010];

bool recurse(int curr){
    int dp [neededSum[curr]+1]; fill(dp, dp+neededSum[curr]+1, 1000000000); dp[0] = 0;
    for(int next : children[curr]){
        if(!recurse(next)) return false;
        int tempDP [neededSum[curr]+1]; fill(tempDP, tempDP+neededSum[curr]+1, 1000000000);
        for(int i = 0; i+neededSum[next] <= neededSum[curr]; i++) tempDP[i+neededSum[next]]= min(tempDP[i+neededSum[next]], dp[i]+black[next]);
		for(int i = 0; i+black[next] <= neededSum[curr]; i++) tempDP[i+black[next]]= min(tempDP[i+black[next]], dp[i]+neededSum[next]);
		for(int i = 0; i <= neededSum[curr]; i++) dp[i] = tempDP[i];
    }
    black[curr] = *min_element(dp, dp+neededSum[curr]+1);
    return black[curr] < 1000000000;
}

int main(){
    //freopen("subrev.in", "r", stdin); freopen("subrev.out", "w", stdout);
    scanf("%d", &N); memset(black, 0, sizeof(black));
    for(int i = 2; i <= N; i++){
        int x; scanf("%d", &x);
        children[x].push_back(i);
    }
    for(int i = 1; i <= N; i++) scanf("%d", &neededSum[i]);
    if(!recurse(1)) cout << "IM";
    cout << "POSSIBLE\n";
    return 0;
}


Measured memory_bytes: 5760
struct Scanner {
    private var elements = [String]()
    private var index = 0

    mutating func peek() -> String {
        while elements.count == index {
            elements = readLine()!.split(separator: " ").map(String.init)
            index = 0
        }
        return elements[index]
    }

    mutating func next() -> String {
        let value = peek()
        index += 1
        return value
    }

    mutating func nextInt() -> Int {
        return Int(next())!
    }

    mutating func nextDouble() -> Double {
        return Double(next())!
    }
}

let MOD = 998244353

struct Zn: CustomStringConvertible {
    let n: Int

    init(_ n: Int) {
        self.n = n
    }

    var description: String {
        String(self.n)
    }

    static var zero = Zn(0)
    static var one = Zn(1)

    static func + (lhs: Self, rhs: Self) -> Self {
        let n = lhs.n + rhs.n
        return Zn(n < MOD ? n : n - MOD)
    }

    static func + (lhs: Self, rhs: Int) -> Self {
        return lhs + Zn(rhs)
    }

    static func + (lhs: Int, rhs: Self) -> Self {
        return Zn(lhs) + rhs
    }

    static func - (lhs: Self, rhs: Self) -> Self {
        let n = lhs.n - rhs.n
        return Zn(n >= 0 ? n : n + MOD)
    }

    static func - (lhs: Self, rhs: Int) -> Self {
        return lhs - Zn(rhs)
    }

    static func - (lhs: Int, rhs: Self) -> Self {
        return Zn(lhs) - rhs
    }

    static func * (lhs: Self, rhs: Self) -> Self {
        Zn((lhs.n * rhs.n) % MOD)
    }

    static func * (lhs: Self, rhs: Int) -> Self {
        return lhs * Zn(rhs)
    }

    static func * (lhs: Int, rhs: Self) -> Self {
        return Zn(lhs) * rhs
    }

    static func += (lhs: inout Self, rhs: Self) {
        lhs = lhs + rhs
    }

    static func += (lhs: inout Self, rhs: Int) {
        lhs = lhs + Zn(rhs)
    }

    static func -= (lhs: inout Self, rhs: Self) {
        lhs = lhs - rhs
    }

    static func -= (lhs: inout Self, rhs: Int) {
        lhs = lhs - Zn(rhs)
    }

    static func *= (lhs: inout Self, rhs: Self) {
        lhs = lhs * rhs
    }

    static func *= (lhs: inout Self, rhs: Int) {
        lhs = lhs * Zn(rhs)
    }

    func pow(_ n: Int) -> Self {
        if n == 0 {
            return Zn(1)
        } else if n % 2 == 1 {
            return self * self.pow(n - 1)
        } else {
            return (self * self).pow(n / 2)
        }
    }

    var inverse: Self {
        self.pow(MOD - 2)
    }
}

var scanner = Scanner()
let K = scanner.nextInt()
print(String(repeating: "ACL", count: K))


Measured memory_bytes: 7668
/*Whose woods these are I think I know.
His house is in the village though;
He will not see me stopping here
To watch his woods fill up with snow.

My little horse must think it queer
To stop without a farmhouse near
Between the woods and frozen lake
The darkest evening of the year.

He gives his harness bells a shake
To ask if there is some mistake.
The only other sound’s the sweep
Of easy wind and downy flake.

The woods are lovely, dark and deep,
But I have promises to keep,
And miles to go before I sleep,
And miles to go before I sleep.*/

#include<bits/stdc++.h>
using namespace std;
#define lli long long int
#define pb push_back
#define fi first
#define se second
#define MOD 1000000007
const int maxn= 100010;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int s=0,w=0;
    cin>>s>>w;
    if(w>=s)
        cout<<"unsafe";
    else
        cout<<"safe";
    cout<<endl;
}

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

#define ld long double

using namespace std;

ld f(int k1, int k2, int k3, vector<vector<vector<ld>>> &dp, int &numPlates) {
    if (dp[k1][k2][k3] > -0.5) {
        // dp already filled
        return dp[k1][k2][k3];
    }

    ld expectedOps = 0;
    expectedOps = ((1.0 * numPlates) / (k1 + k2 + k3));

    ld subPathExpectedOps = 0;

    if (k1) {
        // possible to eat from plates containing one sushi
        // expected ops = prop of choosing plates containing 1 sushi
        // multiplied by expectedOps required if taking that path
        subPathExpectedOps += (1.0 * k1 / (k1 + k2 + k3)) * f(k1 - 1, k2, k3, dp, numPlates);
    }
    if (k2) {
        subPathExpectedOps += (1.0 * k2 / (k1 + k2 + k3)) * f(k1 + 1, k2 - 1, k3, dp, numPlates);
    }
    if (k3) {
        subPathExpectedOps += (1.0 * k3 / (k1 + k2 + k3)) * f(k1, k2 + 1, k3 - 1, dp, numPlates);
    }

    expectedOps += subPathExpectedOps;

    dp[k1][k2][k3] = expectedOps;
    return expectedOps;
}

int main() {
    int N;
    cin >> N;
    vector<int> sushi(N, 0);
    int k1 = 0, k2 = 0, k3 = 0;
    for (int i = 0; i < N; i++) {
        cin >> sushi[i];

        if (sushi[i] == 1) k1 += 1;
        else if (sushi[i] == 2) k2 += 1;
        else if (sushi[i] == 3) k3 += 1;
    }
    vector<vector<vector<ld>>> dp(N + 1, vector<vector<ld>>(N + 1, vector<ld>(N + 1, -1.0)));
    dp[0][0][0] = 0;
    cout << fixed << setprecision(10) << f(k1, k2, k3, dp, N);
    return 0;
}


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

using namespace std;

const int inf = 1e9;

int main () {

  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
  
   int N, K, x, y; cin >> N >> K >> x >> y;
   cout << min(N, K)*x + max(0, N - K)*y << '\n';

  return 0;
}




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

#define fi first
#define se second
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for (int i = 1; i < (n); ++i)
#define drep(i,n) for (int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define all(x) (x).begin(), (x).end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define pb push_back
#define sz(x) (int)(x).size()
#define PQ(T) priority_queue<T, v(T), greater<T> >

using namespace std;
typedef long long ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;

const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;

const int mod = 1000000007;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> h(n);
    rep(i,n) cin >> h[i];
    int ans = 0;
    rep(i,n) {
        if (h[i]>=k) ++ans;
    }
    cout << ans << endl;
    return 0;
}


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

typedef long long ll;
typedef vector<int> vi;

#define PB push_back
#define MP make_pair
#define endl '\n'
#define all(a) (a).begin(),(a).end()
#define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll n,w[105],v[105], dp[100][100005],limit;

ll f(int pos,int weight)
{
    if(pos== n)   return 0;
    if(dp[pos][weight]> 0)
        return dp[pos][weight];
    ll x=0,y=0;
    if(weight>=w[pos])
        x=v[pos]+f(pos+1,weight-w[pos]);
    y=f(pos+1,weight);
    return dp[pos][weight]=max(x,y);


}

int main()
{
    optimize();
    cin>>n>>limit;
    for(int i=0;i<n;i++)
        cin>>w[i]>>v[i];
    ll x=f(0,limit);
    cout<<x;
    return 0;
}


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

#define DEBUG(x) cout<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endl

typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
const int inf = 1000000001;
const ll INF = 1e16;
#define MOD 1000000007
#define mod 1000000009
#define pi 3.14159265358979323846
#define Sp(p) cout<<setprecision(15)<<fixed<<p<<endl;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };

int main() {
	ll x, y;
	cin >> x >> y;
	if (abs(x - y) <= 1) {
		cout << "Brown" << endl;
	}
	else {
		cout << "Alice" << endl;
	}
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define pb push_back
#define fi first
#define se second
#define fr(i,s,e) for(i=s;i<e;i++)
#define ms(arr,val) memset(arr,val,sizeof(arr))
using namespace std;

const int mxn=2e5+1;

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

  int t=1;
  //cin>>t;
  int tt=1;
  while(t--){
    set<int> s;
    int a,b;
    cin>>a>>b;
    s.insert(a+a-1);
    s.insert(b+b-1);
    s.insert(a+b);
    cout<<*s.rbegin();
       //cout<<"Case #"<<tt<<": ";
       //tt++;
    }
  return 0;
}



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

int main(){
  int n;cin>>n;
  int top=n/100;
  int bot=n-top*100;
  
  if(top!=0&&top<=12){
    if(bot!=0&&bot<=12){
      cout<<"AMBIGUOUS"<<endl;
    }else{
      cout<<"MMYY"<<endl;
    }
  }else{
    if(bot!=0&&bot<=12){
      cout<<"YYMM"<<endl;
    }else{
      cout<<"NA"<<endl;
    }
  }
  return 0;
}

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

#define phb push_back
#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
using namespace std;

typedef long long ll;
const ll kInf = 1000000000;

string S;
ll T;
vector< ll > rn;
vector< char > rt;

void solve();
bool rule1();
bool rule2();

int main() {
  cin >> S >> T;
  solve();
  return 0;
}

void solve() {
  bool bb, bc;

  for (int i = 0; i < sz(S); ++i)
    if (!isdigit(S[i]))
      rt.phb(S[i]), S[i] = ' ';

  istringstream iss(S);
  ll tn;
  while (iss >> tn)
    rn.phb(tn);

  bb = rule1();
  bc = rule2();

  if (bb)
    cout << (bc ? "U" : "M") << "\n";
  else
    cout << (bc ? "L" : "I") << "\n";
}

bool rule1() {
  vector< ll > nrn;

  nrn.phb(rn[0]);
  for (int i = 0; i < sz(rt); ++i) {
    if (rt[i] == '+')
      nrn.phb(rn[i + 1]);
    else {
      nrn.back() *= rn[i + 1];
      if (nrn.back() >= kInf)
        return false;
    }
  }

  return accumulate(all(nrn), ll(0)) == T;
}

bool rule2() {
  ll tmp = rn[0];

  for (int i = 0; i < sz(rt); ++i) {
    if (rt[i] == '+')
      tmp += rn[i + 1];
    else
      tmp *= rn[i + 1];

    if (tmp >= kInf)
      return false;
  }

  return tmp == T;
}

Measured memory_bytes: 1220
#include <stdio.h>

int main() {
  int a, b, c;
  scanf("%d %d %d", &a, &b, &c);
  int tmp;
  if (a > b) {
    tmp = b;
    b = a;
    a = tmp;
  }
  if (b > c) {
    tmp = c;
    c = b;
    b = tmp;
  }
  if (a > b) {
    tmp = b;
    b = a;
    a = tmp;
  }
  printf("%d %d %d\n", a, b, c);
  return 0;
}

Measured memory_bytes: 596
"""
import random
import functools
import copy
import bisect
import array
import re
import collections
import heapq
import fractions
import itertools
import string
import math
from operator import itemgetter as ig
from bisect import bisect_left, bisect_right, insort_left, insort_right
from itertools import permutations, combinations, product, accumulate, groupby
from heapq import heappush, heappop
from collections import deque, defaultdict, Counter
import sys
sys.setrecursionlimit(10 ** 7)
# import numpy as np

inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]
ddn9 = ddn + [(0, 0)]
'''for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:'''
"""
import sys
sys.setrecursionlimit(10 ** 7)


def wi(): return list(map(int, sys.stdin.readline().split()))
# WideIntPoint


def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]


def ws(): return sys.stdin.readline().split()


def si(): return int(sys.stdin.readline())  # SingleInt


def ss(): return input()


def hi(n): return [si() for _ in range(n)]


def hs(n): return [ss() for _ in range(n)]  # HeightString


def s_list(): return list(input())


def mi(n): return [wi() for _ in range(n)]  # MatrixInt


def mip(n): return [wip() for _ in range(n)]


def ms(n): return [ws() for _ in range(n)]


def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[
    0]] for _ in range(n)]  # NumberGrid


def grid(n): return [s_list() for _ in range(n)]


def main():
    N = si()
    ans = 0
    for i in range(1, N+1):
        if i % 3 == 0:
            continue
        elif i % 5 == 0:
            continue
        else:
            ans += i
    print(ans)


if __name__ == '__main__':
    main()


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

using namespace std;

# define int long long
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, int> pdi;
typedef pair<ll, ll> pll;

# define S second
# define F first
# define kill(x) return(cout << x << endl, 0)
# define debug(x) cerr<< #x << " : " << x << endl
# define ddebug(x, y) cerr<< #x << " : " << x  << ", " << #y << " : " << y << endl
# define sz(s) (int)s.size()
# define sq(x) (x) * (x)
# define PB(x) push_back(x)
# define smax(x, y) (x) = max((x), (y))
# define smin(x, y) (x) = min((x), (y))
# define all(x) x.begin(), x.end()
# define SP fixed << setprecision(10)

const int MAXN = 100 * 1000 + 10;
int a[MAXN];

int32_t main()
{	
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

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

	sort(a, a + n);

	sum -= a[n - 1];
	int ans = 1;
	for (int i = n - 1; i > 0; i --)
	{
		if (sum * 2 < a[i])
			break;
		sum -= a[i - 1];
		ans ++;
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 1024
// ராஜ்_ஆர்ட்டன்

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

struct fenwick_tree {
	
	vector<int> tree;
	
	fenwick_tree(int sz) {
        	tree.resize(sz, 0);
	}
	
	void add(int id, int val) {
	        for( ; id < tree.size(); id += (id & -id))
			tree[id] += val;
	}
	
	int get(int id) {
	        int ans = 0;
	        for( ; id > 0; id -= (id & -id))
			ans += tree[id];
        	return ans;
	}
	
	int get(int l, int r) {
  	      return get(r) - get(l - 1);
	}
};

void solve() {
	
	int n, N = 1e5 + 5;
	cin >> n;
	
	fenwick_tree ft(N + 1);
	vector<int> a(n + 1);
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		ft.add(a[i], a[i]);
	}
	
	int q;
	cin >> q;
	while(q--) {
		int b, c;
		cin >> b >> c;
		int cur = ft.get(b, b);
		ft.add(b, -cur);
		int cnt = cur / b;
		ft.add(c, c * cnt);
		cout << ft.get(N) << endl;
	}
	
}

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cerr.tie(0);
	// int t; cin >> t; for(int i = 1; i <= t; i++) //cout << "Case #" << i << ": ",
	solve();
	return 0;
}


Measured memory_bytes: 4724
#input = raw_input

s = input()
q = int(input())

inputs = []
n_reverse = 0
for i in range(q):
    input_ = input()
    if input_[0] == "1":
        n_reverse += 1
    inputs.append(input_)

if n_reverse % 2 == 0:
    final_rev = False
else:
    final_rev = True

rev = False
mae = ""
ushiro = ""
for input_ in inputs:
    elms = input_.split(" ")
    t = int(elms[0])
    if elms[0] == "1":
        rev = not rev
    else:
        f = int(elms[1])
        c = elms[2]

        if f == 1:
            if final_rev:
                if rev:
                    mae = c + mae
                else:
                    ushiro = ushiro + c
            else:
                if rev:
                    ushiro = ushiro + c
                else:
                    mae = c + mae
        else:
            if final_rev:
                if rev:
                    ushiro = ushiro + c
                else:
                    mae = c + mae
            else:
                if rev:
                    mae = c + mae
                else:
                    ushiro = ushiro + c

if final_rev:
    s = s[::-1]

out = mae + s + ushiro
print(out)

Measured memory_bytes: 17012
#include <iostream>
using namespace std;
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#define NUM 100

int main()
{
   static long i,j,k,l;
   int r,c;
   static int e[101][101];
   cin >> r >> c;
   for(i=0;i<r;i++) {
      for(j=0;j<c;j++) {
         cin >> e[i][j];
         e[i][c] += e[i][j];
         e[r][j] += e[i][j];
      }
   }
   for(i=0;i<r;i++)
      e[r][c] += e[i][c];

   for(i=0;i<=r;i++) {
      for(j=0;j<c;j++) 
         cout << e[i][j] << ' ';
      cout << e[i][c] << endl;
   }

   return 0;
}

Measured memory_bytes: 1200
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<algorithm>
#include<string>
#include<cstdio>
#include<cstdlib>
#include <clocale>
#include<cmath>
#include<sstream>
#include<set>
#include<stack>
using namespace std;
#define fr(i,n) for(int i=0;i<n;i++)
const int INF=0x3f3f3f3f;
const int MX=1e4+10;
typedef long long ll;
typedef pair<int ,int> p;
int main(){
	int n,k;
	ll num[22];
	cin>>n>>k;
	fr(i,n)cin>>num[i];
	ll ans=1e18;
	fr(i,1<<n){
		int s=0;
		fr(j,n)if((i>>j)&1)s++;
		if(s!=k)continue;
		ll ma=0,temp=0;
		fr(j,n){
			if((i>>j)&1)
			{
				if(num[j]<=ma){
					temp+=ma-num[j]+1;
				     ma++;
				}
				else ma=num[j];
			}
			else
				ma=max(ma,num[j]);
		}
		ans=min(ans,temp);
	}
	cout<<ans<<endl;
    //system("pause");
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main{

    Scanner sc = new Scanner(System.in);

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

    void run() {

        int n = sc.nextInt();
        int k = sc.nextInt();
        Set<Integer> set = new HashSet<>();

        for (int i=0; i<k; i++) {
            int d = sc.nextInt();
            for (int j=0; j<d; j++) {
                int tmp = sc.nextInt();
                set.add(tmp);
            }
        }

        System.out.println(n - set.size());
    }
}


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

int main() {
    double a, b, x;
    cin >> a >> b >> x;
    double s = x / a, ans;
    if (s >= a * b / 2) {
        double h = (a * b - s) * 2 / a;
        ans = atan2(h, a);
    } else {
        double w = s * 2 / b;
        ans = atan2(b, w);
    }
    printf("%.10f\n", ans * 180 / M_PI);
}

Measured memory_bytes: 512
import java.util.Scanner;
 
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int s = sc.nextInt();
        int h = (s/3600);
        int m = (s % 3600)/60;
        int a = s%60;
        System.out.println(h+":"+m+":"+a);
    }
}


Measured memory_bytes: 26304
#include <iostream>

using namespace std;

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

	int cnt = 0;

	for (int i = n; i >= 1; i--) {
		if (i < 10) {
			cnt++;
		}
		else if (i >= 100 && i <= 999) {
			cnt++;
		}
		else if (i >= 10000 && i <= 99999) {
			cnt++;
		}
	}
	cout << cnt;
}



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

#define rep(i,n) for(i=0;i<N;i++)

int main(){
    int N;
    cin >> N;
    int x[N];
    int i;
    rep(i,N){
        cin>>x[i];
    }
    int sum=0;
    rep(i,N){
        sum+=x[i];
    }
    double pos=(double)sum/N;
    int ans1=(int)pos;
    int ans2=(int)(pos+1);
    int min1=0,min2=0;
    rep(i,N){
        min1+=(x[i]-ans1)*(x[i]-ans1);
        min2+=(x[i]-ans2)*(x[i]-ans2);
    }
    if(min1<min2){
        cout<<min1;
    }else{
        cout<<min2;
    }
}


Measured memory_bytes: 3556
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
	int n=0,k=0;
	cin>>n>>k;
	vector<int> arr;
	for(int i=0;i<n;i++){
		int temp=0;
		cin>>temp;
		arr.push_back(temp);
	}
	sort(arr.begin(),arr.end());
	int ans=0;
	for(int i=0;i<k;i++){
		ans+=arr[i];
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 3608
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <utility>
#include <functional>

using namespace std;

#define INF (1 << 30)

int main() {
	int d, n, t[200], a[200], b[200], c[200], dp[201][200] = { 0 };

	cin >> d >> n;
	for (int i = 0; i < d; ++i) {
		cin >> t[i];
	}
	for (int i = 0; i < n; ++i) {
		cin >> a[i] >> b[i] >> c[i];
	}
	fill(dp[0], dp[201], -INF);
	for (int i = 0; i < n; ++i) {
		if (a[i] <= t[0] && t[0] <= b[i]) {
			dp[1][i] = 0;
		}
	}

	for (int i = 1; i < d; ++i) {
		for (int j = 0; j < n; ++j) {
			if (dp[i][j] >= 0) {
				for (int k = 0; k < n; ++k) {
					if (a[k] <= t[i] && t[i] <= b[k]) {
						dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + abs(c[j] - c[k]));
					}
				}
			}
		}
	}

	cout << *max_element(&dp[d][0], &dp[d][n]) << endl;

	return 0;
}

Measured memory_bytes: 3240
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	string str1,str2,str;
	cin >> n;
	cin >> str;
	if(n%2==0)
	{
		str1= str.substr(0,n/2);
		str2= str.substr(n/2,n);
		if(str1==str2)
			cout <<"Yes\n";
		else
			cout << "No\n";
	}
	else
		cout <<"No\n";
	return 0;
}

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

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

    vector<int> R(N);
    for (int i = 0; i < N; i++)
    {
        cin >> R.at(i);
    }

    int max = R.at(1) - R.at(0);
    int min = R.at(0);


    for (int i = 1; i < N; i++)
    {
        int sa;
        sa = R.at(i) - min;
        
        if (max < sa)
        {
            max = sa;
        }
        
        if (R.at(i) < min)
        {
            min = R.at(i);
        }     
    }
    
    cout << max << endl;

}


Measured memory_bytes: 3636
s=input()
j=True
for i in range(len(s)-1):
    if s[i]==s[i+1]:
        print(i+1,i+2)
        j=False
        break
if j:
    for i in range(len(s)-2):
        if s[i]==s[i+2]:
            print(i+1,i+3)
            j=False
            break
if j:
    print("-1 -1")

Measured memory_bytes: 39408
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  
  int N;
  
  cin >> N;
  
  vector<int> A(N);
  for(int i=0; i<N; i++){
    cin >> A.at(i) ;
  }
  
  int M=0;
  
  for(int i=0; i<N; i++){
    
    for(int t=1; t<N-i; t++){
     int S = A.at(i)*A.at(i+t);
     M+=S;
    }
  
  }
  
  cout << M <<endl;
}

Measured memory_bytes: 256