akhauriyash/Code-Regression huggingface dataset:
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <vector>
#include <iostream>
#include <functional>
using namespace std;
#define ll long long

int D;
long long G;
vector<long long> p,c;

int main() {
  cin >> D >> G;
  p.resize(D); c.resize(D);
  for (int i = 0; i < D; ++i) cin >> p[i] >> c[i];

  long long ans = 1000000000000; //ここでは極端に大きければなんでも良い
  for (int mask = 0; mask < (1 << D); mask++) {
    long long sum = 0;

    //答えた問題数
    long long num = 0;

    //p[i]を全完するかしないかをbit全探索
    for (int i = 0; i < D; ++i) {
      if (mask & (1 << i)) sum += c[i] + p[i] * 100 * (i + 1), num += p[i];
    }

    if (sum >= G)
    //総合スコアがG以上になる時、問題数の判定を行なって入れ替える
      ans = min(ans, num);
    else {

      //回答するかしないかをbit全探索
      for (int i = D - 1; i >= 0; i--) {

        //bitが立ってたら次のiに飛ばす
        if (mask & (1 << i)) continue;

        //何問回答するかをここで決める。
        // 2^10 * 100 = 10^5　なので間に合う。
        for (int j = 0; j < p[i]; j++) {
          if (sum >= G) break;
          sum += 100 * (i + 1);
          num++;
        }
      }
      ans = min(ans, num);
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
import math
import sys
import collections
import bisect
readline = sys.stdin.readline


def main():
    a, b, c = map(int, readline().rstrip().split())
    k = int(readline().rstrip())
    i = 0
    while k > i:
        if a >= b:
            b *= 2
            i += 1
            continue
        if b >= c:
            c *= 2
            i += 1
            continue
        print('Yes')
        return
    print('Yes' if c > b and b > a else 'No')


if __name__ == '__main__':
    main()


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

int main(){
    string s1,s2;
    cin >> s1 >> s2;

    swap(s1[0], s1[2]);

    if(s1 == s2) cout << "YES" << endl;
    else cout << "NO" << endl;


    return 0;
}

Measured memory_bytes: 256
N = int(input())
alph = {key + 1: val for key, val in enumerate('abcdefghijklmnopqrstuvwxyz')}
alph[0] = 'z'
answer = ''
while N >= 1:
  answer = alph[N % 26] + answer
  if N == 26:
    break
  N = (N - 1) // 26

print(answer)

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

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

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

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

    typedef long long ll;
using namespace std;

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

  string S, T;
  cin >> S >> T;

  cout << T << S << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <string.h>
using namespace std; using ll = long long; using pll = pair<ll, ll>;
using vl = vector<ll>; using vll = vector<vl>; using vpll = vector<pll>;
int ctoi(char c) {
	switch (c) {
	case '0': return 0; case '1': return 1; case '2': return 2;
	case '3': return 3; case '4': return 4; case '5': return 5;
	case '6': return 6; case '7': return 7; case '8': return 8;
	case '9': return 9;  default: return 0;
	}
}
bool pairCompare(const pll firstElof, pll secondElof)
{
	return firstElof.first > secondElof.first;
}
ll nod(ll F) { return log10(F) + 1; }
//**定義場所**//
//gcd, isPrime, eratos, modinv, bitSearch, dfs, bfs, dijkstra, UnionFind//
ll i, j, k, l, m, n; ll N, M, K, H, W, L; string S;
ll MOD = 1000000007; ll ans = 0; ll INF = 9999999999999;
vl flag, color; vll path;
//***********//

int main() {
	cin >> H;
	ll C = 0;
	while (H > 0) {
		H /= 2;
		ans += pow(2, C);
		C++;
	}
	cout << ans;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int>P;
typedef pair<string, P>SP;


int main(){
    
    ll N;
    cin >> N;
    vector<SP>v(N);
    for(ll i = 0; i < N; i++){
        cin >> v[i].first;
        cin >> v[i].second.first;
        v[i].second.first *= -1;
        v[i].second.second = i + 1;
    }
    sort(v.begin(), v.end());
    for(int i = 0; i < N; i++){
        cout << v[i].second.second << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef pair <int,int> P;
typedef pair<P,int> PP;
vector <PP> vp;

int main(){
  int n,m;
  while(cin>>n>>m && (n||m)){
    vp.clear();
    int na,a;
    cin>>a;
    vp.push_back(PP(P((m/a)*a,a),1));
    na=(m/a)*a;
    for(int i=2;i<=n;i++){
      int am;
      cin>>a;
      if((na/a+1)*a>m) am=(m/a)*a;
      else am=(na/a+1)*a;
      vp.push_back(PP(P(am,a),i));
    }
    sort(vp.begin(),vp.end());
    int ans;
    if(vp[0].f.f==vp[1].f.f && vp[0].f.s==vp[1].f.s) ans=n;
    else ans=vp[0].s;
    cout<<ans<<endl;

  }
  return 0;
}

Measured memory_bytes: 1224
#include<stdio.h>
#include<bits/stdc++.h>
#include<iostream>
#define ll long long
using namespace std;
int main()
{
  ll n ,k;
  cin>>n>>k;
  ll dp[n+1][k+1];
  ll weight[n+1],value[n+1];
  weight[0]=0;
  value[0]=0;
  for(ll i=1;i<n+1;i++)
  {
  	cin>>weight[i];
    cin>>value[i];
  }
  for(ll i=0;i<n+1;i++)
  {
	for(ll j=0;j<k+1;j++)
		dp[i][j]=0;
  }
  for(ll i=1;i<n+1;i++)
  {
    for(ll j=1;j<k+1;j++)
    {
		if(weight[i]>j)
		{
          dp[i][j]=dp[i-1][j];
		}
      	else
        {
			dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);

        }
    }
  }
  cout<<dp[n][k];
  return 0;
}

Measured memory_bytes: 82476
import java.util.*;
 
class Main{
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    
    int x = sc.nextInt();
    int y = sc.nextInt();
    String ans = "No";
    for(int i=0; i<=x; i++){
      int leg = i*2 + (x-i)*4;
      if(y == leg){
        ans = "Yes";
      }
    }
    System.out.println(ans);

    sc.close();
  }
}


Measured memory_bytes: 35836
#if !defined(__clang__) && defined(__GNUC__)
#include <bits/stdc++.h>
#else
#include <cstdlib>
#include <climits>
#include <iostream>
#include <cstdint>
#include <vector>
#include <string>
#include <complex>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <utility>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <regex>
#endif //  !defined(__clang__) && defined(__GNUG__)
#include <boost/lexical_cast.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/multi_array.hpp>
#include <boost/optional.hpp>

using namespace std;

using G = typename std::unordered_map<int64_t, std::vector<int64_t>>;

std::vector<int64_t>
grouping(G& g, const int64_t N)
{
    std::vector<int64_t> group(N, -1);

    for (int64_t i = 0; i < N; ++i) {
        auto f = [&g, &group, col=i](auto F, int64_t from, int64_t prev) -> void {
            group[from] = col;

            for (auto&& to: g[from]) {
                if (group[to] == -1 && to != prev) {
                    F(F, to, from);
                }
            }
        };

        if (group[i] == -1) {
            f(f, i, -1);
        }
    }
    return group;
}


int main()
{
    int64_t N, K, L;
    std::cin >> N >> K >> L;

    G road;
    for (int64_t i = 0; i < K; ++i) {
        int64_t p, q;
        std::cin >> p >> q;
        p--;
        q--;
        road[p].push_back(q);
        road[q].push_back(p);
    }

    G rail;
    for (int64_t i = 0; i < L; ++i) {
        int64_t r, s;
        std::cin >> r >> s;
        r--;
        s--;
        rail[r].push_back(s);
        rail[s].push_back(r);
    }

    const auto road_group = grouping(road, N);
    const auto rail_group = grouping(rail, N);

    std::unordered_map<int64_t, std::unordered_map<int64_t, int64_t>> m;

    // それぞれの都市が属しているグループを集計
    for (int64_t i = 0; i < N; ++i) {
        m[road_group[i]][rail_group[i]] ++;
    }

    // で、i番目の都市はm[道路グループ[i]][鉄道グループ[i]]に属しているから、
    // このループで都市の順番に印字可能。
    for (int64_t i = 0; i < N; ++i) {
        std::cout << m[road_group[i]][rail_group[i]] << " ";
    }

    return 0;
}


Measured memory_bytes: 58056
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/numeric/interval.hpp>
#include <boost/numeric/interval/io.hpp>
#include <boost/any.hpp>
using namespace::std;
namespace mp = boost::multiprecision;
typedef mp::number<mp::cpp_dec_float<32,int64_t>> cfloat;
typedef mp::cpp_int cint;
typedef long long lint;
typedef long long ll;
typedef long double ldouble;
typedef vector<lint> vec;
typedef vector<vector<lint>> mat;
typedef vector<vector<vector<lint>>> mat3;
typedef vector<double> dvec;
typedef vector<vector<double>> dmat;
typedef vector<vector<vector<double>>> dmat3;
typedef vector<string> svec;
typedef vector<vector<string>> smat;
typedef vector<vector<vector<string>>> smat3;
typedef vector<pair<lint,lint>> pvec;
typedef vector<vector<pair<lint,lint>>> pmat;
typedef vector<vector<vector<pair<lint,lint>>>> pmat3;
#define rep(i, n) for(lint i = 0; i < (lint)(n); i++)
#define irep(i) for(lint i = 0;; i++)
#define irep1(i) for(lint i = 1;; i++)
#define irep2(i) for(lint i = 2;; i++)
#define rrep(i, n) for(lint i = (lint)(n-1); i >-1; i--)
#define rrepi(i,a,b) for(lint i = (lint)(b-1); i >a-1; i--)
#define repi(i,a,b) for(lint i=lint(a);i<lint(b);i++)
#define rep2(i,a,b,c) for(lint i=lint(a);i>lint(b);i+=c)
#define all(x) (x).begin(),(x).end()
#define PI 3.141592653589793
#define cout (cout<<fixed<<setprecision(15))
#define dist(x1,y1,x2,y2) (pow(pow(x2-x1,2)+pow(y2-y1,2),0.5))
#define output(v) do{bool f=0;for(auto i:v){cout<<(f?" ":"")<<i;f=1;}cout<<"\n";}while(0)
#define output2(v) for(auto i:v)output(i);
#define input(a,n) lint n;cin>>n;vector<lint>a(n);rep(i,n)cin>>a[i];
#define sum(v) accumulate(all(v),0LL)
#define INF (1LL<<60)
#define IINF (1<<30)
#define LINF 9223372036854775807
#define MOD 1000000007
vector<lint> dx={-1,1,0,0,1,1,-1,-1};
vector<lint> dy={0,0,-1,1,1,-1,1,-1};
inline lint gcd(lint a,lint b){return b?gcd(b,a%b):a;}
inline lint lcm(lint a,lint b){return a*b/gcd(a,b);}
int main(){
    lint n;
    cin>>n;
    vec a(n),b(n+1,0);
    rep(i,n)cin>>a[i];
    rep(i,n)b[i+1]=b[i]+a[i];
    map<lint,lint>mp;
    rep(i,n+1)mp[b[i]]++;
    lint ans=0;
    for(auto i:mp){
        ans+=(i.second)*(i.second-1)/2;
    }
    cout<<ans;
}

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

int main(){
  int N;
  scanf("%d", &N);
  vector<int> dam(N);           //ダムに溜まった水の量
  vector<int> msw(N);          //各山に降った雨量
  int sumw = 0;                           //山に降った雨の総量
  int swe1 = 0;                            //山1に降った雨の量を除いた総量

 /*  2*dam[1] = msw[1] + msw[2],  2*dam[3] = msw[3] + msw[4], 2*dam[5] = msw[5] + msw[6]
        2*dam[7] = msw[7] + msw[8], 2*dam[9] = msw[9] + msw[10];
        sumw = msw[1～11] = dam[1～11]/2 */

  for(int i = 0; i < N; i++){      //各ダムにたまった水量と水量の合計を取得
    cin >> dam[i];
    sumw += dam[i];
  }

  for(int i = 0; i < N / 2; i++)     /*偶数番目を足していけば1番目を除いた総量/2となる*/
    swe1 += 2*dam[2*i + 1];

  msw[0] = sumw - swe1;       //山1に降った雨の量がわかるのであとは芋づる式

  cout << msw[0];
  for(int i = 1; i < N; i++){
    msw[i] = 2 * dam[i-1] - msw[i-1];
    cout << " " << msw[i];
  }
  cout << endl;

}

Measured memory_bytes: 2048
# Knapsack Problem
N, W = [int(x) for x in input().split()]
items = []
for i in range(N):
    items.append(tuple(int(x) for x in input().split()))


DP = [[0] * (W+1) for _ in range(N+1)]
for i in range(N):
    for j in range(W+1):
        v, w = items[i]
        if w <= j:
            DP[i+1][j] = max(DP[i][j], v + DP[i+1][j-w])
        else:
            DP[i+1][j] = DP[i][j]

print(DP[-1][-1])

Measured memory_bytes: 15692
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;
long long n,k;
long long sum=0;
int main(){
	scanf("%lld%lld",&n,&k);
	if(k==0){
		sum=n*n;
	}
	else for(int b=k+1;b<=n;b++){
		if(n%b>=k) sum+=(b-k)*(n/b)+((n%b)+1-k);
	      else sum+=(b-k)*(n/b);
	}
	printf("%lld",sum);
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>
#include <stack>



#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = (int)(n-1); i >= 0; i--)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define all(x) (x).begin(),(x).end()

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

typedef long long ll;

using namespace std;


int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n,m;cin>>n>>m;
  vector<bitset<10>>s(m);
  rep(i,m){
    ll k;cin>>k;
    rep(j,k){
      ll id;cin>>id;
      s[i][id-1]=1;
    }
  }
  vector<ll>oe(m);
  rep(i,m){
    cin>>oe[i];
  }
  ll res=0;
  rep(i,1<<n){
    bitset<10>ti=i;
    ll f=1;
    rep(j,m){
      ll cnt=0;
      rep(k,10){
        if(s[j][k]&&ti[k])cnt++;
      }
      if(cnt%2!=oe[j])f=0;
    }
    if(f)res++;
  }
  cout<<res<<endl;

  return 0;

}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<math.h>
#include<vector>

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, a, n) for (int i = a; i <= (n); ++i)

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

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

    vector<int> a, b;
    rep(i, M) {
       int ia, ib; cin >> ia >> ib;
       a.push_back(ia);
       b.push_back(ib);
    }

    vector<int> route;
    rep(i, N) route.push_back(0);

    rep(j, M) {
        route[a[j] - 1]++;
        route[b[j] - 1]++;
    }

    rep(i, N) cout << route[i] << endl;
    return 0;
}


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

#define int long long
#define rep(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define reps(i, n) for (int (i) = 1; (i) <= (n); (i)++)
#define all(x) (x).begin(), (x).end()
#define bit(n) (1LL << (n))
#define dump(x) cerr << #x " = " << x << endl
typedef vector<int> vint;
typedef pair<int, int> pint;
constexpr double pi = 3.1415926535897932384626433832795028;
constexpr int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
inline int lcm(int a, int b) { return a / gcd(a, b) * b; }
template<typename T1, typename T2> inline bool chmax(T1 &a, const T2 &b) { return a < b && (a = b, true); }
template<typename T1, typename T2> inline bool chmin(T1 &a, const T2 &b) { return b < a && (a = b, true); }
struct SetUp { SetUp() { cout << fixed << setprecision(20); }; } setUp;

int N, K;
int P[220000];
signed main() {
    cin >> N >> K;
    rep(i, N) { cin >> P[i]; }
    set<int> st;
    int cur = 0;
    vector<bool> x(220000);
    rep(i, K) {
        if (i != 0 && P[i] > P[i - 1]) { cur++; }
        else { cur = 0; }
        st.insert(P[i]);
    }
    if (cur >= K - 1) { x[0] = true; }
    int ans = 1;
    rep(i, N - K) {
        if (*st.begin() == P[i] && st.lower_bound(P[i + K]) == st.end()) {}
        else { ans++; }
        st.erase(P[i]);

        if (P[i + K] > P[i + K - 1]) { cur++; }
        else { cur = 0; }

        if (cur >= K - 1) { x[i + 1] = true; }
        st.insert(P[i + K]);
    }

    int a = 0;
    reps(i, N) {
        if (x[i - 1] && !x[i]) { a++; }
    }
    if (a > 0) { ans -= a - 1; }
    cout << ans << endl;

}

Measured memory_bytes: 11264
#include <stdio.h>
#include <iostream>
#include <limits.h>
#include <cstdlib>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <string>
using namespace std;

int main(void){
  long long n,m;
  cin >> n >> m;
  long tt =0;
  long long x = 0,y = 0,z = 0;
  bool ac = false;
  for(x = 0;x <= n; ++x){
    for(y = 0;y <= n; ++y){
      z = n -x -y;
      tt = x*10000 + y*5000 + z*1000;
      if(tt == m && x + y + z == n&& z >= 0){
        ac = true;
        break;
      }
    }
    if(ac)
     break;
  }

  if(!ac)
    x = y = z = -1;


  cout << x << " " << y << " " << z << endl;
}


Measured memory_bytes: 256
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b){ a>b?:a=b; }
template<class T, class C> void chmin(T& a, C b){ a<b?:a=b; }

int main(){
  ll N; cin>>N;
  vector<vector<ll>> dp(N,vector<ll>(3,0));
  rep(i,N){
    ll a,b,c; cin>>a>>b>>c;
    if(i==0){
      dp[i][0]=a, dp[i][1]=b, dp[i][2]=c;
    }else{
      dp[i][0]=max(dp[i-1][1],dp[i-1][2]) +a;
      dp[i][1]=max(dp[i-1][0],dp[i-1][2]) +b;
      dp[i][2]=max(dp[i-1][1],dp[i-1][0]) +c;
    }
  }
  cout<<max(dp[N-1][0],max(dp[N-1][1],dp[N-1][2]))<<endl;
}

Measured memory_bytes: 8784
readints()=parse.(Int,split(readline()))
readint()=parse.(Int,readline())

N=readint()
A=readints()
B=sort(A,rev=true)
nComf=B[1]

nComf+=2*sum(B[2:(1+(N-2)÷2)])
(N-2)%2 == 1 && ( nComf+=B[1+(N-2)÷2+1])
print(nComf)

Measured memory_bytes: 210292
#include<stdio.h>
int main(void){
char s[1001];
int i,sum;
scanf("%s",s);
while(s[0] != '0'){
i=0;
sum=0;
while(s[i]){
sum+=s[i]-'0';
i++;
}
printf("%d\n",sum);
scanf("%s",s);
}
return 0;
}

Measured memory_bytes: 536
import sys
inputs = sys.stdin.readlines()

h, n = map(int, inputs[0].split())
AB = [tuple(map(int, s.split())) for s in inputs[1:]]

dp = [10 ** 9] * (h+1)
dp[0] = 0
for i in range(h):
    for a, b in AB:
        k = min(i + a, h)
        dp[k] = min(dp[k], dp[i] + b)
print(dp[h])

Measured memory_bytes: 41324
H,W=map(int,input().split())
N=int(input())
a=list(map(int,input().split()))

c=[[0 for j in range(W)] for i in range(H)] # 0-initial
cnt=0
for i,ai in enumerate(a):
    for t in range(ai):
        c[cnt//W][cnt%W]=i+1
        cnt+=1
for i in range(H):
    if i%2==1:
        c[i].reverse()

for ci in c:
    print(*ci)

Measured memory_bytes: 42096
N=int(input())
A=list(map(int,input().split()))
total=0
A.sort(reverse=True)
insert=N-1
for i in range(N):
    add=2
    if i==0:
        add=1
    for j in range(add):
        if insert>0:
            total+=A[i]
            insert-=1
print(total)

Measured memory_bytes: 31400
#include <bits/stdc++.h>
#define ll long long
#define lsb(x) (x & -x)

using namespace std;

const int MOD = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("a.in", "r", stdin);

    int n, k;
    cin >> n >> k;
    vector<int> v(n + 1, 0);
    for(int i = 1; i <= n; i ++)
        cin >> v[i];

    vector<vector<int>> dp(n + 1, vector<int> (k + 1, 0));
    vector<vector<int>> sdp(n + 1, vector<int> (k + 1, 0));
    dp[0][0] = 1;
    for(int i = 0; i <= k; i ++)
        sdp[0][i] = 1;

    for(int i = 1; i <= n; i ++)
        for(int j = 0; j <= k; j ++) {
            if(j <= v[i])
                dp[i][j] = sdp[i - 1][j];
            else
                dp[i][j] = (MOD + sdp[i - 1][j] - sdp[i - 1][j - v[i] - 1]) % MOD;

            if(j > 0)
                sdp[i][j] = (dp[i][j] + sdp[i][j - 1]) % MOD;
            else
                sdp[i][j] = dp[i][j];
        }

    cout << dp[n][k];


    return 0;
}


Measured memory_bytes: 79736
#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

const ll inf=998244353;
int num[200005];
char dt[1005][1005];
int doit[4][2]={0,1,1,0,0,-1,-1,0};
struct pp{
    int h,w,mt;
};
class cmp{
public:
    bool operator()(pp a,pp b)
    {
        return a.mt>b.mt;
    }
};
bool vis[1005][1005];
int h,w;
bool check(int nh,int nw)
{
    return nh>=0&&nh<h&&nw>=0&&nw<w&&!vis[nh][nw];
}
int main()
{
    int ch,cw;
    int dh,dw;
    scanf("%d%d%d%d%d%d",&h,&w,&ch,&cw,&dh,&dw);
    ch--,cw--,dh--,dw--;
    for(int i=0;i<h;i++)
        scanf("%s",dt[i]);
    priority_queue<pp,vector<pp>,cmp> qe;
    qe.push({ch,cw,0});
    while(qe.size())
    {
        pp t=qe.top();qe.pop();
        if(vis[t.h][t.w])
            continue;
        if(t.h==dh&&t.w==dw)
        {
            cout<<t.mt;
            return 0;
        }
        vis[t.h][t.w]=1;
        for(int i=0;i<4;i++)
        {
            int nh=t.h+doit[i][0],nw=t.w+doit[i][1];
            if(check(nh,nw))
            {
                if(dt[nh][nw]=='.')
                {
                    qe.push({nh,nw,t.mt});
                }
                else
                {
                    for(int j=-2;j<=2;j++)
                    {
                        int hh,ww;
                        if(i%2==0)
                            hh=nh+j,ww=nw;
                        else
                            hh=nh,ww=nw+j;
                        if(check(hh,ww)&&dt[hh][ww]=='.')
                        {
                            qe.push({hh,ww,t.mt+1});
                        }
                        if(i%2==0)
                            hh=nh+j,ww=nw+doit[i][1];
                        else
                            hh=nh+doit[i][0],ww=nw+j;
                        if(check(hh,ww)&&dt[hh][ww]=='.')
                        {
                            qe.push({hh,ww,t.mt+1});
                        }
                    }
                }
            }
        }
    }
    cout<<-1;
    return 0;
}


Measured memory_bytes: 5940
#include<stdio.h>
int main(void)
{   
    int N,L[10];
    int i,j,tmp,S=0;
  
    scanf("%d",&N);
    
    for(i=0;i<N;i++)
      scanf("%d",&L[i]);
  
    for(i=0;i<N;i++){
      for(j=i+1;j<N;j++){
        if(L[i]>L[j]){
          tmp=L[i];
          L[i]=L[j];
          L[j]=tmp;
        }
      }
    }
  
    for(i=0;i<N-1;i++)
      S+=L[i];
    
    if(S>L[N-1]) printf("Yes\n");
    else printf("No\n");
  
    return 0;
}


Measured memory_bytes: 1660
n, k = gets.split.map(&:to_i)
as = gets.split.map(&:to_i)

counts = as.each.with_object(Array.new(n + 1, 0)) do |a, h|
  h[a] += 1
end.sort!

ans = 0
until counts.size <= k
  ans += counts.shift
end

puts ans


Measured memory_bytes: 18432
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctype.h>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

//4方向ベクトル→↑←↓
int dx[] ={1,0,-1,0};
int dy[] ={0,-1,0,1};

//参考http://d.hatena.ne.jp/otaks/20111026/1319629788 

int main()
{
  map<string,int> dp;
  string str ="01234567";
  dp[str] = 0;
  queue<string> bfs;
  bfs.push(str);
  while(!bfs.empty()){
    str = bfs.front();
    bfs.pop();
    int t;
    for(int i = 0;i <8;i++){//0の位置を探す
      if(str[i] =='0')
	t = i;
    }

    if(t > 0&&t !=4){//左と交換
      string tm = str;
      swap(tm[t],tm[t-1]);
      if(dp.find(tm) ==dp.end()){//一致するものがないので追加する
	bfs.push(tm);
	dp[tm] =dp[str]+1;
      }
    }
    if(t>3){//上と入れ替え
      string tm = str;
      swap(tm[t],tm[t-4]);
      if(dp.find(tm) ==dp.end()){
	bfs.push(tm);
	dp[tm] =dp[str] + 1;
      }
    }
    if(t<7&&t !=3){//右と入れ替え
      string tm = str;
      swap(tm[t],tm[t+1]);
      if(dp.find(tm)==dp.end()){
	bfs.push(tm);
	dp[tm] = dp[str]+1;
      }
    }
    if(t <4){
      string tm =str;
      swap(tm[t],tm[t+4]);
      if(dp.find(tm) ==dp.end()){
	bfs.push(tm);
	dp[tm] = dp[str]+1;
      }
    }
  }
  while(1){
  string pz;
  char c;
  for(int i = 0; i < 8;i++){
    if(!(cin >>c))
      return 0;
    pz +=c;
  }
  cout <<dp[pz]<<endl;
  }
  return 0;
}

Measured memory_bytes: 3444
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<climits>
using namespace std;
#define INF LLONG_MAX
#define P pair<ll, ll>
#define N 101
#define ll long long int

ll loop(ll left, ll right);
void resetDp();
ll n;
vector<P> cost;
ll dp[N][N];

int main(){
    resetDp();
    cin >>n;
    for(int i = 0; i < n; i++){
        ll top, bottom;
        cin >>top >>bottom;
        cost.push_back( make_pair(top, bottom) );
    }
    cout <<loop(0, n - 1) <<endl;
    return 0;
}

ll loop(ll left, ll right){
    if(left == right) return 0;
    else if(dp[left][right] != INF) return dp[left][right];
    else {
        ll ret = INF;
        for(int i = left; i < right; i++){
            ret = min(ret, loop(left, i) + loop(i + 1, right) + (cost[left].first * cost[i].second * cost[i + 1].first * cost[right].second));
        }
        return dp[left][right] = ret;
    }
}

void resetDp(){
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            dp[i][j] = INF;
        }
    }
}

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

int n, m, i, j;
int main(){
        while(cin >> n >> m && n > 0 || m > 0){
                int ans = 0;
                vector<int> h(n);
                vector<int> w(m);
                for (i = 0; i < n; i++) cin >> h[i];
                for (i = 0; i < m; i++) cin >> w[i];

                map<int, int> mp;
                for (i = 0; i < n; i++){
                        int tmp = h[i];
                        mp[tmp]++;
                        for (j = i + 1; j < n; j++){
                                tmp += h[j];
                                mp[tmp]++;
                        }
                }
                for (i = 0; i < m; i++){
                        int tmp = w[i];
                        ans += mp[tmp];
                        for (j = i + 1; j < m; j++){
                                tmp += w[j];
                                ans += mp[tmp];
                        }
                }
                cout << ans << endl;
        }
        return 0;
}



Measured memory_bytes: 20928
#include <stdio.h>
#include <string.h>

char S[12];
int L;
long long N[12], total;

void f(int i, long long val, long long sum)
{
	if(i > L)
	{
		if(!val) total += sum;
	}
	else
	{
		f(i+1, N[i+1], sum + val);
		f(i+1, val*10+N[i+1], sum);
	}
}

int main()
{
	scanf("%s", S);
	L = strlen(S);
	
	for(int i=0; i<L; i++)
		N[i+1] = S[i]-'0';
	
	f(1, N[1], 0);
	printf("%lld", total);
	
	return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
int max(int n,int m){
    if(n>m)return n;
    else return m;
}
int min(int n,int m){
    if(n<m)return n;
    else return m;
}
int main(){
    int n,m,temp,x,y,a[10000],tx,ty;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)a[i]=i;
    for(int i=0;i<m;i++){
        scanf("%d%d%d",&temp,&x,&y);
        if(temp==1){
            if(a[x]==a[y])printf("1\n");
            else printf("0\n");
        }
        else{
            tx=a[x];
            ty=a[y];
            for(int i=0;i<n;i++)if(a[i]==tx||a[i]==ty)a[i]=min(tx,ty);
        }
    }
}

Measured memory_bytes: 2636
#include <bits/stdc++.h>
using namespace std;
#define rep(i,c) for(int i=0;i<c;++i)
int main(){
int x,y;
cin >> x>> y;
if((x+y)%3==0||x%3==0||y%3==0){
    cout << "Possible" << endl;
}else{
    cout << "Impossible" << endl;
}
return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define inf 1000000000
#define INF 1000000000000000
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define PLL pair<ll,ll>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
#define IN(a,n) rep(i,n){ cin>>a[i]; }
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define PI 3.14159265
#define F first
#define S second
#define PB push_back
#define EB emplace_back
void init(){
  cin.tie(0);
  ios::sync_with_stdio(false);
}

int n;
ll dp[110][4][4][4];

int main(){
  cin>>n;
  dp[0][3][3][3]=1;

  // 0=='A' 1=='C' 2=='G' 3=='T'

  rep(i,n){
    rep(a,4) rep(b,4) rep(c,4) rep(d,4){
      if(a==0&&b==2&&d==1)continue;
      if(a==0&&c==2&&d==1)continue;
      if(b==0&&c==1&&d==2)continue;
      if(b==0&&c==2&&d==1)continue;
      if(b==2&&c==0&&d==1)continue;
      dp[i+1][b][c][d]+=dp[i][a][b][c];
      dp[i+1][b][c][d]%=M;
    }
  }

  ll ans=0;
  rep(i,4) rep(j,4) rep(k,4){
    ans+=dp[n][i][j][k];
    ans%=M;
  }

  cout<<ans<<endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define loop(i,a,b) for (int i=a; i<b; ++i)
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll H1, M1, H2, M2, K;
    cin >> H1 >> M1 >> H2 >> M2 >> K;
    ll time;
    if (H1==H2) time=M2-M1;
    else time= (60-M1) + ((H2-H1-1)*60) + M2;
    cout << time-K << "\n";
    return 0;
}

Measured memory_bytes: 3584
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <sstream>
#include <set>
#include <map>
#include <iostream>
#include <utility>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <limits.h>
#include <cstring>
#include <tuple>
#include <cassert>
#include <numeric>
#include <iomanip>
using namespace std;
// type alias
typedef long long LL;
typedef pair< int , int > II;
typedef tuple< int, int, int > III;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<vector<int>> VVI;
typedef unordered_map<int,int> MAPII;
typedef unordered_set<int> SETI;
template<class T> using VV=vector<vector<T>>;
// minmax
template<class T> inline T SMIN(T& a, const T b) { return a=(a>b)?b:a; }
template<class T> inline T SMAX(T& a, const T b) { return a=(a<b)?b:a; }
// repetition
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)
#define REPE(i,n)  for(int i=0;i<=(n);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define FORR(x,arr) for(auto& x:arr)
#define SZ(a) int((a).size())
// collection
#define ALL(c) (c).begin(),(c).end()
// DP
#define MINUS(dp) memset(dp, -1, sizeof(dp))
#define ZERO(dp) memset(dp, 0, sizeof(dp))

// stdout
#define println(args...) fprintf(stdout, ##args),putchar('\n');

// debug cerr
#define TRACE true
#define dump(x) if(TRACE) { cerr << #x << " = " << (x) << endl; }
#define dump2(x,y) if(TRACE) { cerr << #x << " = " << (x) << ", " << #y << " = " << (y) << endl; }
#define dump3(x,y,z) if(TRACE) { cerr << #x << " = " << (x) << ", " << #y << " = " << (y) << ", " << #z << " = " << (z) << endl; }
#define dump4(x,y,z,a) if(TRACE) { cerr << #x << " = " << (x) << ", " << #y << " = " << (y) << ", " << #z << " = " << (z) << ", " << #a << " = " << (a) << endl; }
#define dumpf(args...) if(TRACE) { fprintf(stderr, ##args); putchar('\n'); }
#define dumpAR(ar) if(TRACE) { FORR(x,(ar)) { cerr << x << ','; } cerr << endl; }
template<class Iter> void dumpc(Iter begin, Iter end) { if (TRACE) { for(; begin!=end; ++begin) { cerr<<*begin<<','; } cerr<<endl; } }

/*
 
 12/2/2018 ABC114
 
 21:09-21:18 AC
 
 https://img.atcoder.jp/abc114/editorial.pdf
 
 */

// $ ../batch 755 | diff 755.out -
// $ g++ -std=c++14 -Wall -O2 -D_GLIBCXX_DEBUG -fsanitize=address 755.cpp && ./a.out
int N;

LL res=0;
VI X={3,5,7};

void dfs(LL cur, int mask) {
  if(cur>N) return;
  if(mask==7) ++res;
  REP(i,3) dfs(10LL*cur+X[i],mask|(1<<i));
}
void solve() {
  dfs(0,0);
  cout<<res<<endl;
}

void dfs_org(int p, LL cur) {
  if(cur<=N) {
    int n=cur;
    SETI S;
    while(n>0) S.emplace(n%10),n/=10;
    res+=(SZ(S)==3);
  }
  if(p>=9) return;

  REP(i,3) {
    dfs_org(p+1,10*cur+X[i]);
  }
}
void solve_org() {
  dfs(0,0);    
  cout<<res<<endl;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  
  cin>>N;
  solve();
  
  return 0;
}


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

using namespace std;

#if 1
#define DEBUG(x) do{cerr << #x << "=" << x << endl;}while(0);
#else
#define DEBUG
#endif

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

	cout << 3 * r * r << endl;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <cfloat>
#define zero(x) (((x)>0?(x):-(x))<eps)

#define pause cout << " press ansy key to continue...",  cin >> chh
#define file_r(x) freopen(x,  "r",  stdin)
#define file_w(x) freopen(x,  "w",  stdout)
#define lowbit(x) ((x) & (-x))
#define repit(i, c) for (__typeof__((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repe(i, u) for (int i = head[u]; i != -1; i = nxt[i])
#define repd(i, n) for (int i = (n - 1); i >= 0; i--)
#define FOR(i, n, m) for (int i = (n); i <= (m); i++)
#define FORD(i, n, m) for (int i = (n); i >= (m); i--)
#define pb push_back
#define X first
#define Y second
#define ins insert
#define rb rbegin
#define be begin
#define er erase
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define SZ(c) (c).size()
#define ALL(c) (c).begin(), (c).end()
#define sqr(r) ((r) * (r))
#define dis(x1, y1, x2, y2) (((x1) - (x2)) * ((x1) - (x2)) + ((y1) - (y2)) * ((y1) - (y2)))
#define FASTIO ios::sync_with_stdio(false);cin.tie(0)

#define sc(x) cout << #x" = " << x << endl
#define sc2(x, y) cout << #x" = " << x << " " << #y" = " << y << endl
#define sc3(x, y, z) cout << #x" = " << x << " " << #y" = " << y << " " << #z" = " << z << endl
#define sc4(x, y, z, w) cout << #x" = " << x << " " << #y" = " << y << " " << #z" = " << z << " " << #w" = " << w << endl

#define in(n) scanf("%d", &n)
#define in2(n, m) scanf("%d %d", &n, &m)
#define in3(x, y, z) scanf("%d %d %d", &x, &y, &z)

using namespace std;
int chh;

typedef vector<int> vi;
typedef set<int> si;
typedef map<int, int> mii;
typedef pair<int, int> pii;
typedef pair<int, pii> pi3;
typedef vector< pair<int, int> > vpii;
typedef long long LL;

const int N = 200005;

int n;
int a[N];
map<LL, LL> q;

int main() {
	LL tmp, ans, d;
	while (~in(n)) {
		tmp = 0, ans = 0;
		q.clear();
		rep (i, n) {
			in(a[i]);
			q[tmp += a[i]]++;
		}
		d = 0;
		rep (i, n) {
			ans += q[d];
			d += a[i];
			q[d]--;
		}
		cout << ans << '\n';
	}
	return 0;
}


Measured memory_bytes: 13568
#include<stdio.h>
#define N 100
int main()
{
  int p[N+1],m[N+1][N+1],a,q,l,j,k,i,t;
  // float inf = INFINITY;
  scanf("%d",&a);


  for(i=1;i<=a;i++)
    {
      scanf("%d %d",&p[i-1],&t);
    }
  p[a]=t;
  for(i=1;i<=a;i++)m[i][i]=0;
  for(l=2;l<=a;l++){
    for(i=1;i<a-l+2;i++)
      {
	j=i+l-1;
	m[i][j]=1000000;
	for(k=i;k<=j-1;k++)
	  {
	    q=(m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]);
	    if(m[i][j] >=  q) m[i][j]=q;
	  }
      }
  }
  printf("%d\n",m[1][a]);
  return 0;
}
      



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

int main()
{
	int n, l;
	cin >> n >> l;
	vector<string> s(n);
	for (int i=0; i<n; i++) cin >> s.at(i);
	sort(s.begin(), s.end());
	for (int i=0; i<s.size(); i++) cout << s.at(i);

	return 0;

}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
const int N = 1e5 + 5;
int n;
int x[N];
int y[N];
int arr[N];
vector < pair < int , pair < int , int > > > v;
int parent[N];
long long ans;
int cost(int a , int b){
	return min(abs(x[a] - x[b]) , abs(y[a] - y[b]));
}
int find(int node){
	if(parent[node] == node){
		return node;
	}
	return parent[node] = find(parent[node]);
}
int main(){
	scanf("%d" , &n);
	for(int i = 1 ; i <= n ; ++i){
		scanf("%d %d" , x + i , y + i);
		arr[i] = i;
		parent[i] = i;
	}
	sort(arr + 1 , arr + 1 + n , [](int a , int b){
		return x[a] < x[b];
	});
	for(int i = 1 ; i < n ; ++i){
		v.push_back({cost(arr[i] , arr[i + 1]) , {arr[i] , arr[i + 1]}});
	}
	sort(arr + 1 , arr + 1 + n , [](int a , int b){
		return y[a] < y[b];
	});
	for(int i = 1 ; i < n ; ++i){
		v.push_back({cost(arr[i] , arr[i + 1]) , {arr[i] , arr[i + 1]}});
	}
	sort(v.begin() , v.end());
	for(auto it : v){
		if(find(it.second.first) != find(it.second.second)){
			ans += it.first;
			parent[find(it.second.first)] = find(it.second.second);
		}
	}
	printf("%lld\n" , ans);
}

Measured memory_bytes: 6388
x, y = map(int, input().split())

if x * y == 0:
    if x > y:
        print(x-y+1)
    else:
        print(y-x)
elif x * y < 0:
    if x > y:
        print(abs(-y-x)+1)
    else:
        print(min(y-x, abs(x+y)+1))
else:
    if x > y:
        print(abs(y-x)+2)
    else:
        print(y-x)

Measured memory_bytes: 3060
def main():
    h, n = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(n)]
    dp =[0]*(h+max(a for a,b in ab))
    for i in range(1, h+1):
        dp[i] = min(dp[i-a]+b for a,b in ab)
    print(dp[h])
      
if __name__ == '__main__':
    main()

Measured memory_bytes: 3648
def b_sort(ca)
  c = ca.dup
  s = 0
  c.sort_by{|i| [i[1], s += 1]}
end

def s_sort(ca)
  c = ca.dup
  c.size.times do |i|
    m = i
    i.upto(c.size - 1) do |j|
      if c[j][1] < c[m][1]
        m = j
      end
    end
    c[m], c[i] = c[i], c[m]
  end
  c
end

gets
a = gets.split.map do |e|
  e =~ /(\w)(\d+)/
  [$1, $2.to_i]
end
b, c = [b_sort(a), s_sort(a)].map do |d|
  d.map(&:join).join(' ')
end
puts b
puts 'Stable'
puts c
puts b == c ? 'Stable' : 'Not stable'

Measured memory_bytes: 8756
#include <bits/stdc++.h>
#define ALL(a) (a).begin(),(a).end()
#define N_MAX 1000
#define ll long long int
using namespace std;

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

	int ans = 0;
	for (int i = 1; i < N-1; i++) {
		if (S[i - 1] == 'A' && S[i] == 'B' && S[i + 1] == 'C')ans++;
	}

	cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//BEGIN CUT HERE
template<typename T> 
struct BIT{
  int n;
  vector<T> bit;
  //1-indexed
  BIT():n(-1){}
  BIT(int n,T d):n(n),bit(n+1,d){}
  
  T sum(int i){
    T s=0;
    for(int x=i;x>0;x-=(x&-x))
      s+=bit[x];
    return s;
  }
  void add(int i,T a){
    if(i==0) return;
    for(int x=i;x<=n;x+=(x&-x))
      bit[x]+=a;
  }
  
  T query(int l,int r){
    return sum(r-1)-sum(l-1);
  }

  void rebuild(){
    vector<T> prev(bit);
    vector<T> dump(n+1);
    for(int i=1;i<=n;i++) dump[i]=query(i,i+1);
    bit.assign(n+1,0);
    
    for(int i=1;i<=n;i++){
      bit[i]+=dump[i];
      if(i+(i&-i)<=n) bit[i+(i&-i)]+=bit[i];
    }
    for(int i=1;i<=n;i++) assert(prev[i]==bit[i]);
  }
};
//END CUT HERE

signed AOJ_DSL2B(){
  int n,q;
  cin>>n>>q;
  BIT<Int> bit(n+100,0);
  for(int i=0;i<q;i++){
    int c,x,y;
    cin>>c>>x>>y;
    if(c) cout<<bit.query(x,y+1)<<endl;
    else bit.add(x,y);
    if(i%1000==0) bit.rebuild();
  }
  return 0;
}
/*
  verified on 2018/05/18
  http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B&lang=jp
*/

signed main(){
  AOJ_DSL2B();
  return 0;
}



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

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  auto ok = [&](int a, int b, int c) {
    bool A = a != b and (a + b) > c;
    bool B = b != c and (b + c) > a;
    bool C = c != a and (c + a) > b;
    return A and B and C;
  };
  int cnt = 0;
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      for (int k = j + 1; k < n; k++) {
        cnt += ok(a[i], a[j], a[k]);
      }
    }
  }
  cout << cnt << '\n';
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define MOD2 998244353
float PHI = 1.6180339;
//const floarrt  PI_F=3.14159265358979f;
#define endl "\n"    
//typedef long long floarrt;
#define int long long
//#define floarrt unsigned long long

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin>>n;
    int arr[n+10];
    for(int i=0;i<n;i++)
    cin>>arr[i];
    int cnt=0;
    sort(arr,arr+n);
    for( int i = n-1; i >= 1; i--){ 
        int l = 0, r = i-1; 
        while( l < r){ 
            if( arr[l] + arr[r] > arr[i]){  
                cnt += r - l ;  
                r--;   
            } 
            else 
                l++;   
        } 
    }
    cout<<cnt<<endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        double l = 100000;
        for (int i = 1; i <= n; i++) {
            l *= 1.05;
            if (l%1000 != 0) {
                l += (1000 - (l%1000));
            }
        }
        System.out.println((long)l);
    }
}

Measured memory_bytes: 25980
a,b,h,m =  gets.chomp.split.map(&:to_i)
kakua = (h*30 + m * 0.5)
kakub = m*6 
pi =Math::PI
kaku = (kakua-kakub) / 180
cosc=Math.cos(kaku * pi )
c = Math.sqrt(a*a+b*b-2*b*a*cosc)
puts c

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

int main(){
	int a[3],d;
	for(int i=0;i<3;i++)cin >> a[i];
	cin >> d;
	if(abs(a[2]-a[0])<=d)cout << "Yes" << endl;
	else if(abs(a[2]-a[1])<=d && abs(a[1]-a[0])<=d)cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

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

using namespace std;

using ll = long long;
using ld = long double;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    // cout << setprecision(8) << setiosflags(ios::fixed);

    int n, m;
    cin >> n >> m;

    vector<int> a;
    a.reserve(2 * n);
    for (int i = 0, x; i < n; ++i) {
        cin >> x;
        a.push_back(x);
    }

    vector<pair<int, int>> cb(m);
    for (int i = 0; i < m; ++i) {
        cin >> cb[i].second >> cb[i].first;
    }
    sort(cb.begin(), cb.end());
    reverse(cb.begin(), cb.end());

    int size = 0;
    for (int i = 0; i < m; ++i) {
        if (n < size) continue;
        for (int j = 0; j < cb[i].second && size < n; ++j) {
            a.push_back(cb[i].first);
            ++size;
        }
    }

    sort(a.begin(), a.end(), greater<int>());

    ll sum = 0;
    for (int i = 0; i < n; ++i)
        sum += a[i];

    cout << sum << endl;

    return 0;
}


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

using namespace std;

int main(int argc, char *argv[]) {
    int A, B;
    cin >> A >> B;
    string s;
    cin >> s;

    size_t pos = s.find('-');
    bool ok(true);
    if (pos == A) {
        if (s.size() == A + B + 1) {
            for (int i = 0; i < s.size(); i++) {
                if (i == A) continue;
                if (s[i] - '0' >= 0 && s[i] - '0' <= 9) {
                } else {
                    ok = false;
                    break;
                }
            }
        } else {
            ok = false;
        }
    } else {
        ok = false;
    }
    cout << ((ok) ? "Yes" : "No") << endl;
    
    return 0;
}


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

int testa(string s, string t, int i){
    int answ=0;
    for(int j=0;j<t.size();j++){
        answ+=(s[i+j]!=t[j]);
    }
    return answ;
}

int main(){
    string s,t;

    cin >> s >> t;

    int answ = s.size();
    for(int i=0;i<=s.size()-t.size();i++){
        answ = min(answ,testa(s,t,i));
    }
    cout << answ <<'\n';

    return 0;
}

Measured memory_bytes: 3640
#include<bits/stdc++.h>
#define LL long long
#define ULL unsigned  long long
#define maxn (LL)1e7
#define INF 0x3f3f3f3f
#define inf 0x7fffffff
#define PI  acos(-1.0)
#define pb push_back
#define re register LL
const double eps = 0.0000001;
using namespace std;
typedef pair<LL,LL> pii;
typedef long long ll;
const ll N=1e5+5;
ll a[N];
int main()
{
    ll n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    ll flag=0,m=0;
    for(ll i=1;i<n;i++)
    {
        if(a[i]>=a[i+1]) flag++;
        if(a[i]<a[i+1]){m=max(m,flag);flag=0;}
    }
    cout<<max(m,flag);
}


Measured memory_bytes: 1024
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

N, M = rl()
A = [-1]
prev_a = -float('inf')
for i in range(M):
	a = ri()
	if a-prev_a == 1:
		print(0)
		exit()
	A.append(a)
	prev_a = a
A.append(N+1)

dp = [0]*(N+5)
dp[0] = 0
dp[1] = 1
for i in range(N+5-2):
	dp[i+2] = dp[i+1] + dp[i]
ans = 1
for i in range(len(A)-1):
	ans *= dp[A[i+1]-A[i]-1]
	ans = ans % mod
print(ans)


Measured memory_bytes: 516636
//
//  main.cpp
//  A- Frog 1
//  Category: Dynamic Programming
//  Created by dz2701 on 8/25/20.
//  Copyright © 2020 dz2701. All rights reserved.
//

#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5+1;
const int INF = 1e9;

int N, dp[MAX];
//dp[i] is the minimum cost possible to reach ith stone.
int stone[MAX]; //input of heights of stones
int main(int args, char* argvs[]){
    cin >> N;
    for(int i=1;i<=N;i++)cin >> stone[i];
    stone[0]=INF;
    //initialize dp. dp[0] will not be possible (does not exist) so set it to impossible value
    dp[0] = INF; dp[1] = 0;
    fill(&dp[2],&dp[N],0);
    for(int i=2;i<=N;i++){
        dp[i] = min(dp[i-1]+abs(stone[i]-stone[i-1]), dp[i-2]+abs(stone[i]-stone[i-2]));
    }
    cout << dp[N];
    return 0;
}


Measured memory_bytes: 4380
package main

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

//=====I/O=====

var (
	sc = bufio.NewScanner(os.Stdin)
	wr = bufio.NewWriter(os.Stdout)
)

func scanInt() int {
	sc.Scan()
	a,_ := strconv.Atoi(sc.Text())
	return a
}

func scanInts(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ { res[i] = scanInt() }
	return res
}

func scanText() string {
	sc.Scan()
	return sc.Text()
}

func printInts(a ...int) {
	for i, e := range a {
		fmt.Fprint(wr, e)
		if i != len(a)-1 { fmt.Fprint(wr, " ") }
	}
	fmt.Fprintln(wr)
	wr.Flush()
}

//=====main=====

func main() {
	sc.Split(bufio.ScanWords)

	n := scanInt()

	c := 1 << uint(n)

	a := make([][]test, n)
	ans := 0

	for i := 0; i < n; i++ {
		in := scanInt()
		for j := 0; j < in; j++ {
			a[i] = append(a[i], test{scanInt()-1, scanInt()})
		}
	}

	for i := 0; i < c; i++ {
		ok := true
		for f := 0; f < n; f++ {
			if i >> uint(f) & 1 == 1 {
				for _, e := range a[f] {
					x, y := e.x, e.y
					if i >> uint(x) & 1 != y {
						ok = false
					}
				}
			}
		}
		if ok {
			count := 0
			for j := 0; j < n; j++ {
				if i >> uint(j) & 1 == 1 {
					count++
				}
			}
			ans = max(ans, count)
		}
	}

	fmt.Println(ans)
}

type test struct {
	x int
	y int
}

func min(a ...int) int {
	res := a[0]
	for i := 1; i < len(a); i++ {
		if res > a[i] { res = a[i] }
	}
	return res
}

func max(a ...int) int {
	res := a[0]
	for i := 1; i < len(a); i++ {
		if res < a[i] { res = a[i] }
	}
	return res
}


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

using namespace std;
# define M_PI 3.14159265358979323846
# define epsi 1e-9
# define F first
# define S second
# define REP(i,a,b) for(int i=a;i<=b;i++)
using ll = long long int;
const int MOD = 1e9 + 7;
int main()
{
    int n;
    cin>>n;
    int rem=n%10;
    if(rem==2 || rem==4 || rem==5 || rem==7 || rem==9)
    {
        cout<<"hon";
    }
    else if(rem==0 || rem==1 || rem==6 || rem==8)
    {
        cout<<"pon";
    }
    else
    {
        cout<<"bon";
    }
    
}

Measured memory_bytes: 3632
#ABC095C 全列挙
def main():
    import sys, math
    A,B,C,X,Y = map(int, sys.stdin.readline().split())
    ans = float('inf')
    for i in range(10**5+1):
        tmp = i*2*C + max(0, (X-i)*A) + max(0, (Y-i)*B)
        ans = min(tmp, ans)
        if i > X and i > Y:
            break
    print(ans)  

if __name__=='__main__':
    main()


Measured memory_bytes: 3060