akhauriyash/Code-Regression huggingface dataset:
dic = {}

n, m = map(int, input().split())
ar_a = map(int, input().split())
for i in range(m):
  b, c = map(int, input().split())
  if c not in dic:
    dic[c] = 0
  dic[c] += b

ar = []
for c in sorted(dic.keys(), reverse=True):
  cnt = dic[c]
  if cnt > n:
    cnt = n
  ar += [c] * cnt
  if len(ar) >= n:
    break

if len(ar) < n:
  ar += [0] * (n-len(ar))

sum = 0
for x, y in zip(ar, sorted(ar_a)):
  sum += max([x,y])
print(sum)


Measured memory_bytes: 28580
#include <bits/stdc++.h>
//#define int long long
using namespace std;
int main() {
  string c1, c2;
  cin >> c1 >> c2;
  string ans = "NO";
  if (c1[0] == c2[2] && c1[1] == c2[1] && c1[2] == c2[0]) ans = "YES";
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <fstream>
#include <sstream>
#include <iomanip>
#define ll long long

using namespace std;

long long MOD = 1000000007;

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

    int cnt=0;
    for(int i=0; i<3; i++){
        if(S[i]==T[i]){
            cnt++;
        }
    }
    cout << cnt << endl;

}

Measured memory_bytes: 256
def is_ok(a, b, c):
    if a == b and b == c:
        return False

    s = sorted([a,b,c])
    if s[0] == s[1] and s[2] == b:
        return True
    if s[1] == s[2] and (s[1] == b or s[2] == b):
        return True
    if s[1] == b:
        return True
    return False

n = int(input())
p = tuple(map(int, input().split()))

ans = 0
for i in range(n - 2):
    if is_ok(p[i], p[i+1], p[i+2]):
        ans = ans + 1

print(ans)


Measured memory_bytes: 3064
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<math.h>
#include<bitset>
using namespace std;
using ll=long long;
using ld=long double;
using pint=pair<int,int>;
using pll=pair<ll,ll>;
#define LONG_INF 9223372036854775807
#define INF 1000000000LL
#define EPS 1e-10
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define dump(a) rep(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define all(v) v.begin(),v.end()
#define pb push_back


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

    int a, b, c;
    cin >> a >> b >> c;
    if(a==b & a!=c) cout << "Yes"<< endl;
    else if(a==c & a!=b) cout << "Yes" << endl;
    else if(b==c & b!=a) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

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

int n,W;
int v[100],w[100];
int dp[101][10001];

int func(int i,int j){
    if (dp[i][j]>=0) {
        return dp[i][j];
    }
    
    int res;
    if(i==n){
        res=0;
    }
    else if (j<w[i]){
        res=func(i+1, j);
    }
    else{
        res=max(func(i+1, j), func(i+1, j-w[i])+v[i]);
    }
    return dp[i][j]=res;
}

int main(){
    cin>>n>>W;
    for (int i=0; i<n; i++) {
        cin>>v[i]>>w[i];
    }
    for (int i=0; i<101; i++) {
        for (int j=0; j<10001; j++) {
            dp[i][j]=-1;
        }
    }
    cout<<func(0, W)<<endl;
    return 0;
}

Measured memory_bytes: 7028
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
#define ll long long
#define mod 100000007
#define rep(i, n) for (int i = 0; i < n; ++i)
using Graph = vector<vector<int>>;
ll lcm(ll a, ll b)
{
    return a * b / __gcd(a, b);
}

int main()
{
    int N, M, C;
    cin >> N >> M >> C;
    vector<int> B(M);
    for (int i = 0; i < M;i++)
    {
        cin >> B[i];
    }
    vector<vector<int>> A(N, vector<int>(M));
    
    for (int i = 0; i < N;i++)
    {
        for (int j = 0; j < M;j++)
        {
            cin >> A[i][j];
        }
    }
    int AC = 0;
    for (int i = 0; i < N;i++)
    {
        int pre = 0;
        for (int j = 0; j < M; j++)
        {
            pre += A[i][j] * B[j];
        }
        pre += C;
        if(pre > 0){
            AC++;
        }
    }
    cout << AC << endl;
}

Measured memory_bytes: 384
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <algorithm>

using namespace std;
using lint = long long;
constexpr int MOD = 1000000007, INF = 1010101010;
constexpr lint LINF = 1LL << 60;

#ifdef _DEBUG
#include "../../../library/library/debug_template.cpp"
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(...) ((void)0)
#endif

struct init {
	init() {
		cin.tie(nullptr); ios::sync_with_stdio(false);
		cout << fixed << setprecision(10);
	}
} init_;

int main() {

	long double A, B, H, M;
	cin >> A >> B >> H >> M;

	cout << sqrtl(A * A + B * B - 2 * A * B * cos(3.1415926535 * (H * 30 + 0.5 * M - 6 * M) / 180)) << "\n";

	return 0;
}



Measured memory_bytes: 4184
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC164D
{
    class Program
    {
        static void Main(string[] args)
        {
            var S = Console.ReadLine();

            int N = 2019;

            int[] anss = new int[N];
            anss[0]++;

            int temp = 0;
            int d = 1;
            for (int i = S.Length - 1; i >= 0; i--)
            {
                int jou = S.Length - i - 1;

                int temp2 = int.Parse(S[i].ToString());

                temp = (temp2 * d + temp) % N;
                anss[temp]++;
                d = (d * 10) % 2019;
            }


            int ans = 0;
            for (int i = 0; i < N; i++)
            {
                if (anss[i] < 2) continue;
                var a = anss[i] * (anss[i] - 1) / 2;
                ans += a;
            }

            Console.WriteLine(ans);
            Console.ReadKey();
        }
    }
}


Measured memory_bytes: 21624
#include <algorithm>
#include <cassert>
// #include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
// #include <random>
#include <set>
#include <stack>
#include <string>
// #include <unordered_map>
// #include <unordered_set>
#include <utility>
#include <vector>

/*
unsigned seed1 = std::chrono::system_clock::now().time_since_epoch().count();
mt19937 g1.seed(seed1);
*/
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<pii, pii> ppiipii;
typedef pair<int, ppiipii> pippiipii;
typedef pair<int, pii> pipii;
typedef pair<pii, int> ppiii;
typedef pair<int, ppiii> pippiii;
typedef pair<int, ll> pill;
typedef pair<int, double> pid;
// note to self, the below two triggers someone
typedef pair<ll, ll> pll;
typedef pair<ll, int> plli;
typedef long double ld;

ll l[200005];

int main() {
  int n;
  scanf("%d", &n);
  for(int i = 0; i < n; i++) {
    scanf("%lld", &l[i]);
    l[i] -= i;
  }
  sort(l, l+n);
  ll med = l[n/2];
  for(int i = 0; i < n; i++) {
    l[i] -= med;
  }
  ll ret = 0;
  for(int i = 0; i < n; i++) {
    ret += abs(l[i]);
  }
  printf("%lld\n", ret);
}


Measured memory_bytes: 1792
import java.util.Scanner;
public class Main {
	public static void main(String[] args)throws Exception{
		Scanner stdIn=new Scanner(System.in);
		int N=stdIn.nextInt();
		int p[]=new int[N];
		int ans=0;
		for(int i=0;i<N;i++){
			p[i]=stdIn.nextInt()-1;
		}
		for(int i=0;i<N-1;i++){
			if(p[i]==i){
				int k=p[i];
				p[i]=p[i+1];
				p[i+1]=k;
				ans++;
			}
		}
		if(p[N-1]==N-1)
			ans++;
		System.out.println(ans);
	}
}


Measured memory_bytes: 50392
use proconio::input;

#[allow(unused_imports)]
use proconio::marker::{Bytes, Chars, Usize1};
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
#[allow(unused_imports)]
use std::ops::*;

#[derive(Clone, Debug, Default)]
struct Struct;




//#[proconio::fastout]
fn main() {
    input! {
        n: u64,
    }
    let mut x = n;
    let mut v = Vec::new();

    for p in 2.. {
        if x < p*p {
            if x != 1 {
                v.push((x,1));
            }
            break;
        }
        let mut e = 0;
        while x % p == 0 {
            x /= p;
            e += 1;
        }
        v.push((p,e));
    }

    let mut ans = 0;
    while let Some((_p,mut e)) = v.pop() {
        for j in 1.. {
            if e >= j {
                e -= j;
                ans += 1;
            } else {
                break;
            }
        }
    }

    println!("{}", ans);
}


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

int main() {
	int n; cin >> n;
  	int odd = 0;
  	for (int i = 1; i <= n; i++) {
      odd += (i & 1);
    }
  	cout << setprecision(10) << (odd / double(n)) << endl;
}

Measured memory_bytes: 256
def solv():
    count = 0
    for i in field:
        if i > 1:
            print("War")
            return
        if i == 1:
            count += 1
        if count == N+1:
            print("No War")
            return


N, M, X, Y = map(int, input().split())
x = [int(i)+100 for i in input().split()]
y = [int(i)+100 for i in input().split()]
field = [0 for _ in range(201)]
field[X+100] += 1
field[Y+100] += 2
for i in x:
    field[i] += 1
for i in y:
    field[i] += 2
solv()


Measured memory_bytes: 3064
import java.util.*;

public class Main {
  public static void main(String[] args) {    
	Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int count = 0;
    int[] arr = new int[n];
    for(int i = 0; i < n; i++) {
      arr[i] = sc.nextInt();
    }
    boolean even = true;
    while(even) {
      for(int i = 0; i < n; i++) {
        if(arr[i] % 2 == 1) {
          even = false;
          break;
        } else {
          arr[i] = arr[i] / 2;
        }
      }
      if(even) {
        count++;
      }
    }
    System.out.println(count);
  }
}

Measured memory_bytes: 21972
import sys
import os

def file_input():
    f = open('../Beginner_Contest_166/input.txt', 'r')
    sys.stdin = f

def main():
    #file_input()
    # int(input())
    N,M=map(int, input().split())   #N:展望台 N:道
    H=list(map(int, input().split()))   #高さ

    c=0
    nice=[True]*N
    for i in range(M):
        A,B=map(int, input().split())
        # print("H["+str(A)+"]"+str(H[A-1])+" H["+str(B)+"]:"+str(H[B-1]))
        if H[A-1]>H[B-1]:
            if nice[B-1]:
                nice[B-1]=False
                c+=1
        elif H[A-1]<H[B-1]:
            if nice[A-1]:
                nice[A-1]=False
                c+=1
        elif H[A-1]==H[B-1]:
            if nice[B-1]:
                nice[B-1]=False
                c+=1
            if nice[A-1]:
                nice[A-1]=False
                c+=1

    print(N-c)


if __name__ == '__main__':
    main()


Measured memory_bytes: 20148
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <stack>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m;
int s1,s2,t1,t2;
char a[1005][1005];
bool b[1005][1005];
int dp[1005][1005];
int h[5]={-1,0,1,0},l[5]={0,-1,0,1};
struct edge{
	int x;
	int y;
	edge(){}
	edge(int X,int Y){x=X,y=Y;}
};
queue <edge> q2;
bool bfs(int x,int y,int z)
{
	deque <edge> q;
	q.push_front(edge(x,y));
	while(!q.empty())
	{
		edge u=q.front();
		q.pop_front();
		if(u.x==t1 && u.y==t2)
		{
			printf("%d",dp[u.x][u.y]);
			return true;
		}
		if(b[u.x][u.y])
		{
			continue;
		}
		b[u.x][u.y]=1;
		for(int i=0;i<4;i++)
		{
			if(u.x+h[i]>=1 && u.x+h[i]<=n && u.y+l[i]>=1 && u.y+l[i]<=m && a[u.x+h[i]][u.y+l[i]]!='#')
			{
				dp[u.x+h[i]][u.y+l[i]]=min(dp[u.x+h[i]][u.y+l[i]],dp[u.x][u.y]);
			//	b[u.x+h[i]][u.y+l[i]]=1;
				q.push_front(edge(u.x+h[i],u.y+l[i]));
			}
		}
		for(int i=u.x-2;i<=u.x+2;i++)
		{
			for(int j=u.y-2;j<=u.y+2;j++)
			{
				if(i<=0 || j<=0 || i>n || j>m || a[i][j]=='#' || b[i][j]==1)
				{
					continue;
				}
				dp[i][j]=min(dp[i][j],dp[u.x][u.y]+1);
				q.push_back(edge(i,j)); 
			}
		}
	}
	return false;
}
int main() 
{
	scanf("%d %d",&n,&m);
	scanf("%d %d\n%d %d",&s1,&s2,&t1,&t2);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
			dp[i][j]=0x3f3f3f3f;
		}
	}
	dp[s1][s2]=0;
	if(bfs(s1,s2,0)==false)
	{
		printf("-1");
	}
	return 0;
}

Measured memory_bytes: 10064
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  int a,b,m;
  cin>>a>>b>>m;
  vector<int> A(a);
  vector<int> B(b);
  rep(i,a){
    cin>>A[i];
  }
  rep(i,b){
    cin>>B[i];
  }
  int min_cost=200010;
  rep(i,m){
    int x,y,c,now_cost;
    cin>>x>>y>>c;
    now_cost=A[x-1]+B[y-1]-c;
    min_cost=min(min_cost,now_cost);
  }
  sort(A.begin(),A.end());
  sort(B.begin(),B.end());
  int z = A[0] + B[0];
  min_cost=min(min_cost,z);
  cout<<min_cost<<endl;
}

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

using namespace std;

const long long NMAX = 1e5;
const long long BMAX = 60;

long long v[NMAX+2], N, K;
long long ans = 0;
long long nr[BMAX+2], sp_nr[BMAX+2], best_sp[BMAX+2];

int main()
{
    long double a,b;
    cin >> a >> b;
    cout << setprecision(12) << a / b << '\n';
    return 0;

    }


Measured memory_bytes: 256
#include <bits/stdc++.h>
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 REP(i, x, n) for(int i = x; i < n; i++)

int main(){
    int n; cin >> n;
    string ans = "Three";
    rep(i, n){
        char c; cin >> c;
        if(c == 'Y') ans = "Four";
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;

LL n;

int main() {
	scanf("%lld" , &n);
	LL ans = 0;
	for (int i = 1; i < n; ++i) {
		ans += (n - 1) / i;
	}
	printf("%lld" , ans);
	return 0;
}

Measured memory_bytes: 3256
using System;

namespace ABC141
{
    class ABC141_A
    {
        static void Main(string[] args)
        {
            var ans = Console.ReadLine();

            if ("Sunny" == ans)
                Console.WriteLine("Cloudy");
            else if ("Cloudy" == ans)
                Console.WriteLine("Rainy");
            else
                Console.WriteLine("Sunny");
        }
    }
}

Measured memory_bytes: 11092
A, B, C, X, Y = map(int, raw_input().split())

cost = 0

if A + B >= 2 * C:
    cost += 2 * C * min(X, Y)
else:
    cost += (A + B) * min(X, Y)

diff = abs(X-Y)
if X > Y:
    if A > 2 * C:
        cost += 2 * C * diff
    else:
        cost += A * diff
else:
    if B > 2 * C:
        cost += 2 * C * diff
    else:
        cost += B * diff

print(cost)


Measured memory_bytes: 2568
#include "bits/stdc++.h"
#define int long long
#define all(c) (c).begin(), (c).end()
#define cpresent(c,x) ((c).find(x) != (c).end()) 
#define vpresent(c,x) (find(all(c),x) != (c).end())
#define endl '\n'
#ifdef LOCAL
#include "/home/iggaboi/Desktop/CP/debug.h"
#else
#define debug(x...)
#endif
using namespace std;

int n;

void solve(){
    cin >> n;
    vector<int> xors(n);
    int xx = 0;
    for(int i = 0; i < n; ++i){
        cin >> xors[i];
        xx ^= xors[i];
    }
    for(int i = 0; i < n; ++i)
        xors[i] = xx ^ xors[i];
    
    for(int i = 0; i < n; ++i)
        cout << xors[i] << " ";
}

int32_t main(){
	ios_base::sync_with_stdio(false),cin.tie(nullptr);
	// int t; cin >> t;
	// while(t--)
		solve();
	return 0;
}


Measured memory_bytes: 4756
#include <bits/stdc++.h>
#define int long
#define ll long long
#define MOD (int)(1000000007)
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
int gcd(int a,int b){return b ? gcd(b,a%b) : a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}

map<ll,int> prime_factor(ll n){
    map<ll,int> ret;
    for(ll i=2; i*i<=n; i++){
        while(n % i == 0){
            ret[i]++;
            n /= i;
        }
    }
    if(n != 1) ret[n]=1;
    return ret;
}

main(){
    int N; cin >> N; map<ll,int> m;
    for(int i=1;i<=N;i++){
        for(auto p:prime_factor(i)){
            m[p.first]+=p.second;
        }
    }
    ll ans=1;
    for(auto p:m){
        ans=ans*(p.second+1)%MOD;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int x,cnt,ans,p,k;
int main()
{
	ans = 0;
	p = 1;
	scanf("%d",&x);
	for (int i = 2; i <= x; i++)
	{
		k = i;
		cnt = 0;
		while(k % 2 == 0)
		{
			cnt++;
			k/=2;
		}
		if(cnt > ans)
		{
			ans = cnt;
			p = i;
		}
	}
	printf("%d\n",p);
	return 0;
}

Measured memory_bytes: 256
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]

INF = W + 10
dp = [[INF for _ in range(N*10**3+10)] for _ in range(N+1)]

dp[0][0] = 0
for sum_v in range(N*10**3+1):
    for n in range(N):
        Wi = wv[n][0]
        Vi = wv[n][1]
        if sum_v - Vi >= 0:
            dp[n+1][sum_v] = min(dp[n][sum_v], dp[n][sum_v-Vi] + Wi)
        dp[n+1][sum_v] = min(dp[n][sum_v], dp[n+1][sum_v])

ans = 0
for sum_v in range(len(dp[N])):
    if dp[N][sum_v] <= W:
        ans = sum_v

print(ans)


Measured memory_bytes: 171372
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        boolean[] lefts = new boolean[n];
        int leftmax = 0;
        lefts[0] = true;
        for (int i = 0; i < n && leftmax < n - 1; i++) {
            if (lefts[i]) {
                for (int j = leftmax + 1; j - i <= arr[i] / 10 && j < n; j++) {
                    lefts[j] = true;
                    leftmax = j;
                }
            }
        }
        boolean[] rights = new boolean[n];
        int rightmin = n - 1;
        rights[n - 1] = true;
        for (int i = n - 1; i >= 0 && rightmin > 0; i--) {
            if (rights[i]) {
                for (int j = rightmin - 1; i - j <= arr[i] / 10 && j >= 0; j--) {
                    rights[j] = true;
                    rightmin = j;
                }
            }
        }
        if (lefts[n - 1] && rights[0]) {
            System.out.println("yes");
        } else {
            System.out.println("no");
        }
    }
}



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

int main() {
    int H, W;
    
    while(true) {
        cin >> H >> W;
        
        if(H==0 && W==0) break;
        for(int i=0; i<H; i++){
            for(int j=0; j<W; j++){
                if(i==0 || i==H-1 || j==0 || j==W-1){
                    cout << "#";
                }else{
                    cout << ".";
                }
                
            }
            cout << "\n";
        }
        cout << endl;
    }
    return 0;
}

Measured memory_bytes: 2988
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
const int INF = 1e9;
const int MOD = 1000000007;
ll n,m,v,p;
vector<ll> a(n);

bool ok(int x){
  if(x >= n-p) return true;
  if(a[x] + m < a[n-p]) return false;
  ll res = 0;
  rep(i,n){
    if(i <= x) res += m;
    else if(i >= n-p+1) res += m;
    else{
      res += a[x]-a[i]+m;
    }
  }
  return res >= v*m;
}
 
int main() {
  cin >> n >> m >> v >> p;
  a.resize(n);
  rep(i,n) cin >> a.at(i);
  sort(a.begin(),a.end());
  int left = -1,right = n;
  while(right - left > 1){
    int mid = (left + right)/2;
    if(ok(mid)) right = mid;
    else left = mid;
  }
  
  cout << n-right << endl;
  
  return 0;
}


    

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <tuple>
#include <utility>
#include <set>
#include <numeric>
#include <queue>
#include <sstream>
#include <map>
#include <unordered_map>
#include <cmath>
using namespace std;
using LLI = long long int;

#define Rep(i, N) for (int i = 0; i < N; i++)

int main(int argc, char *argv[])
{
    int N;
    string S;
    cin >> N >> S;

    int m = S.substr(1).find(S[0]) != string::npos;
    for (int i=2; i<N-1; i++) {
        string s1 = S.substr(0, i);
        string s2 = S.substr(i);
        if (s2.find(s1.substr(s1.size() - m - 1)) != string::npos) {
            m++;
        }
    }

    cout << m << endl;
 
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()

ans = []
if n == 0:
    print(0)
    quit()
while 1:
    if n == 0:
        break
    if n % 2:
        ans.append(1)
        n -= 1
    else:
        ans.append(0)
    n //= -2
print(''.join(list(map(str,ans[::-1]))))

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

using namespace std;

long long n, m;

int main(){
	scanf("%lld%lld", &n, &m);
	
	if(n == 1 && m == 1)
	return 0 * printf("%lld\n", 1);
	if(n == 1)
	return 0 * printf("%lld\n", m - 2);
	if(m == 1)
	return 0 * printf("%lld\n", n - 2);
	
	printf("%lld\n", 1LL * (n - 2) * (m - 2));
}


Measured memory_bytes: 256
#include <cassert>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <iomanip>
#include <string>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <numeric>
using namespace std;

string to_string(bool x) {
	return x ? "true" : "false";
}

string to_string(char x) {
	return string(1, x);
}

string to_string(string s) {
	return '"' + s + '"';
}

string to_string(const char *s) {
	return to_string((string) s);
}

template<typename A, typename B>
string to_string(pair<A, B> p) {
	return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template<typename A>
string to_string(A v) {
	bool first = true;
	string res = "{";
	for (const auto &x : v) {
		if (!first) {
			res += ", ";
		}
		first = false;
		res += to_string(x);
	}
	res += "}";
	return res;
}

void debug_out() {
	cerr << endl;
}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << to_string(H);
	debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define all(x) (x).begin(), (x).end()
#define sz(a) (int)(a).size()
#define pb push_back
#define fi first
#define se second
#define two(a) (1LL << (a))
#define has(mask, i) ((mask >> i) & 1)
//#define int ll

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector < int >;
using vll = vector < ll >;
using vvi = vector < vector < int > >;
using vpii = vector < pii >;
using ld = long double;
using vs = vector < string >;

//mt19937_64 rnd((unsigned long) chrono::high_resolution_clock::now().time_since_epoch().count());

int N;
vi A, B, C;

void solve() {
  cin >> N;
  A.resize(N);
  B.resize(N);
  C.resize(N - 1);
  for (auto &x : A)
    cin >> x;
  for (auto &x : B)
    cin >> x;
  for (auto &x : C)
    cin >> x;
  int ans = 0;
  for (int i = 0; i < N; i++) {
    ans += B[i];
    if (i && A[i - 1] + 1 == A[i]) {
      auto id = A[i - 1];
      --id;
      ans += C[id];
    }
  }
  cout << ans;
}

signed main() {
#ifdef LOCAL
	freopen("xxx.in", "r", stdin);
	freopen("xxx.out", "w", stdout);
	auto start_time = clock();
#endif

	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.setf(ios::fixed | ios::showpoint);
	cout.precision(12);
	cerr.setf(ios::fixed | ios::showpoint);
	cerr.precision(4);

	solve();

#ifdef LOCAL
	auto end_time = clock();
	cerr << "time: " << (end_time - start_time) * 1.0 / CLOCKS_PER_SEC << endl;
#endif

	return 0;
}


Measured memory_bytes: 256
//Radhe Radhe
#include<bits/stdc++.h>
#define godspeed  ios_base:: sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define ll long long
#define ld long double
#define fi first
#define se second
#define mp make_pair
#define rep1(i,a,b)    for(ll i=a; i<=b; i++)
#define repVect(i,n)    for(ll i=0; i<sum.size(); i++)
#define fixed cout.setf(ios::fixed);
#define Precise cout.precision(7);
#define yes cout<<"YES"<<'\n';
#define no cout<<"NO"<<'\n';
using namespace std;

int main()
{
    godspeed
    ll  i,j,k,l,n,ans=1;
    cin>>n>>k;
    while(n--)
    {
       // cout<<ans<<" "<<k;
        ans+=min(ans,k);
    }

    cout<<ans<<endl;


       return 0;
}





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

#define sup ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define ll long long


int main()
{
	sup;
    
    ll n, x, t;
    cin >> n >> x >> t;

    cout << ((n + x - 1) / x) * t << endl;
    
    return 0;
}

Measured memory_bytes: 3624
import itertools
N = int(input())
LX, LY = [], []
RX, RY = [], []
DX, DY = [], []
UX, UY = [], []

for _ in range(N):
  x,y,d = input().split()
  x,y = int(x), int(y)
  if d == 'L':
    LX.append(x)
    LY.append(y)
  elif d == 'R':
    RX.append(x)
    RY.append(y)
  elif d == 'U':
    UX.append(x)
    UY.append(y)
  else:
    DX.append(x)
    DY.append(y)

INF = 10**18
fixed_x = [min(UX + DX + [INF]), max(UX + DX + [-INF])]
fixed_y = [min(LY + RY + [INF]), max(LY + RY + [-INF])]

R_x = [min(RX + [INF]), max(RX + [-INF])]
L_x = [min(LX + [INF]), max(LX + [-INF])]
U_y = [min(UY + [INF]), max(UY + [-INF])]
D_y = [min(DY + [INF]), max(DY + [-INF])]


# 2点が衝突する時刻を除けば1次関数
T = [0]

for x1,x2 in itertools.product(L_x, R_x):
  if x1 in [-INF, INF] or x2 in [-INF, INF]:
    continue
  T.append((x1 - x2) / 2)
for x1,x2 in itertools.product(L_x, fixed_x):
  if x1 in [-INF, INF] or x2 in [-INF, INF]:
    continue
  T.append(x1 - x2)
for x1,x2 in itertools.product(R_x, fixed_x):
  if x1 in [-INF, INF] or x2 in [-INF, INF]:
    continue
  T.append(x2 - x1)
  
for x1,x2 in itertools.product(D_y, U_y):
  if x1 in [-INF, INF] or x2 in [-INF, INF]:
    continue
  T.append((x1 - x2) / 2)
for x1,x2 in itertools.product(D_y, fixed_y):
  if x1 in [-INF, INF] or x2 in [-INF, INF]:
    continue
  T.append(x1 - x2)
for x1,x2 in itertools.product(U_y, fixed_y):
  if x1 in [-INF, INF] or x2 in [-INF, INF]:
    continue
  T.append(x2 - x1)
  
T = sorted(set(t for t in T if t >= 0))
T.append(10 ** 9)

def calc_x(t):
  # t秒後の横幅
  right = fixed_x[1]
  left = fixed_x[0]
  for x in [R_x[1]+t, L_x[1]-t]:
    if right < x:
      right = x
  for x in [R_x[0]+t, L_x[0]-t]:
    if left > x:
      left = x
  return right - left

def calc_y(t):
  # t秒後の横幅
  right = fixed_y[1]
  left = fixed_y[0]
  for y in [U_y[1]+t, D_y[1]-t]:
    if right < y:
      right = y
  for y in [U_y[0]+t, D_y[0]-t]:
    if left > y:
      left = y
  return right - left

def F(x1,x2,y1,y2):
  # x は x1からx2に向かう1次関数
  # y は y1からy2に向かう1次関数
  # t in [0,1] で関数を作る
  # x = (x2-x1)t + x1
  # y = (y2-y1)t + y1
  p,q,r,s = x2-x1, x1, y2-y1, y1
  a,b,c = p*r, p*s + q*r, q*s
  # f(t) = at^2 + bt + c
  if a <= 0:
    # 直線 or 上に凸
    return min(x1*y1, x2*y2)
  t0 = -b/(2*a)
  if t0 < 0 or t0 > 1:
    return min(x1*y1, x2*y2)
  return min(a*t0*t0 + b*t0 + c, a+b+c, c)
  
L = len(T)
X = [calc_x(t) for t in T]
Y = [calc_y(t) for t in T]

answer = 10 ** 18

for i in range(L-1):
  x1, x2 = X[i], X[i+1]
  y1, y2 = Y[i], Y[i+1]
  s = F(x1,x2,y1,y2)
  if answer > s:
    answer = s

print(answer)

Measured memory_bytes: 12364
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <numeric>
#include <cmath>
#include <limits>
#include <bitset> 
#include <iterator> 
#include <map>
#include <queue>
#include <set>
#define rep(i,n) for(ll i=0;i<(n); ++i)
#define per(i,n) for(ll i=n-1;i>=0; --i)
#define all(x) (x).begin(),(x).end()
#define _GLIBCXX_DEBUG
using namespace std;
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; }
const long long INF = 1LL << 60;
typedef long long ll;
ll MOD = 1000000007;
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

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

	ll n,sum = 0;
	cin >> n;
	vector<ll>a(n+2,0);
	rep(i, n)cin >> a[i+1];
	vector<ll>cost;
	rep(i, n+1)cost.push_back(abs(a[i + 1] - a[i]));
	sum = accumulate(all(cost),0LL);
	for (ll i = 1; i < n+1;i++) {
		cout << sum - abs(a[i+1]-a[i]) - abs(a[i-1]-a[i]) + abs(a[i+1]-a[i-1]) << endl;
	}
} 


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



int main() {
	int n;
	cin>>n;
	int a[2][n];
	for(int i=0;i<2;i++){
	    for(int j=0;j<n;j++){
	        cin>>a[i][j];
	    }
	}
	int b[n];
	int c[n];
	b[0]=a[0][0];
	for(int i=1;i<n;i++){
	    b[i]=b[i-1]+a[0][i];
	}
	c[n-1]=a[1][n-1];
	for(int i=n-2;i>=0;i--){
	    c[i]=c[i+1]+a[1][i];
	}
	int sum=0;
	int ans=0;
	for(int i=0;i<n;i++){
	    ans=max(ans,b[i]+c[i]);
	    //sum=sum+ans;
	    //cout<<c[i];
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <iomanip>
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <tuple>
#include <climits>
#include <algorithm>
#include <cmath>
using namespace std;

typedef long long LL;
typedef vector<int> VI;
typedef vector<double> VD;
typedef vector<LL> VLL;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<vector<int>> VVI;
typedef vector<vector<long long>> VVLL;
typedef vector<vector<bool>> VVB;
typedef vector<vector<double>> VVD;

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define all(a) (a).begin(),(a).end()

const int MOD = 1000000007;

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

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

void debug(VI &arr){
	int n=arr.size();
	rep(i,n){
		cout<<arr.at(i)<<endl;
	}
}

void debug(VVI &board){
	int h = board.size();
	int w = board.at(0).size();
	rep(i,h){
		rep(j,w){
			cout << board.at(i).at(j) << " ";
		}
		cout<<endl;
	}
}

void debug(VVLL &board){
	int h = board.size();
	int w = board.size();
	rep(i,h){
		rep(j,w){
			cout<<board.at(i).at(j)<<" ";
		}
		cout<<endl;
	}
}

LL gcd(LL a,LL b){
	return b==0?a:gcd(b,a%b);
}

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

int main(){
	//cout<<fixed;
	//cout<<setprecision(9)<<...
	map<string, int> d={
		{"SUN",0},
		{"MON",1},
		{"TUE",2},
		{"WED",3},
		{"THU",4},
		{"FRI",5},
		{"SAT",6}
	};
	string s;cin>>s;
	cout<<7-(d[s])<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<iostream>

using namespace std;
int main(){
	int D;
	scanf("%d",&D);
	if(D == 25) printf("Christmas\n");
	 if(D == 24) printf("Christmas Eve\n");
	 if(D == 23) printf("Christmas Eve Eve\n");
	 if(D == 22) printf("Christmas Eve Eve Eve\n");
	return 0;	
}

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

#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define mp make_pair
#define input freopen("input.txt","r",stdin);
#define output freopen("output.txt","w",stdout);
#define fast_io ios::sync_with_stdio(NULL), cin.tie(NULL), cout.tie(NULL);
#define fix cout << fixed << setprecision(15);
//#define left left228
//#define right right228
//#define next next228
#define rank rank228
//#define prev prev228
#define y1 y1228
#define dout if(debug) cout
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int> ;
using pll = pair<ll, ll>;
using pci = pair<char, int>;
using vi = vector<int> ;
using vll = vector<ll> ;
using vpii = vector<pii> ;
const ll infll = 1e18 + 3;
const int maxn = 1e6 + 77;
const int nmax = 1e6 + 577;
const ll basell = 1e18 + 3;
const int mod = 1e9 + 7;
const ld eps = 1e-7;
const int inf = 1009000999;
const int nv = 100505;
const int baseint = 1000200013;
const ld PI = acos(-1.0);
inline bool EQ(ld a, ld b) { return fabs(a-b) < 1e-9; }
inline bool IF(int a, int b, int c) { return (a >= b && a <= c); }
inline bool IFS(int a, int b, int c) { return (a > b && a < c); }
template<typename T> inline istream &operator>> (istream &_in, vector<T> &_v) { for (auto &_i : _v) { _in >> _i; } return _in; }
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
//typedef pair<int, int> pt;
//#define x first
//#define y second
//ifstream cin("input.txt");
//ofstream cout("output.txt");
/*
sort(a, a + n, [&](pair<pt, int> a, pair<pt, int> b){if (a.x.x != b.x.x)
        return a.x.x < b.x.x; return a.x.y > b.x.y;});
for(int c : s)
for(int &i : a) cin >> i;
for(int c = 'a'; c <= 'z'; ++c)
vector<vector<ll>> dp(n, vector<ll>(n+2));
__int128;
char 0 = int 48;
char c = cin;
int h = (int)c - 48;
*/

/*char memory[(int)1e8];

char memorypos;

inline void * operator new(size_t n){
    char * ret = memory + memorypos;
    memorypos += n;
    return (void *)ret;
}

inline void operator delete(void *){}
*/

int a[nv];

int dp[nv];

int inline solve() {
    //input;//,output;
    //fix;
    fast_io;
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    dp[0] = 0;
    for (int i = 1; i <= k; ++i) {
        int pos = 0, neg = 0;
        for (int j = 0; j < n; ++j) {
            if(i - a[j] < 0) break;
            if(dp[i - a[j]] == 1){
                pos++;
            } else {
                neg++;
            }
        }
        if(neg != 0) {
            dp[i] = 1;
        }
    }
    if(dp[k]) cout << "First";
    else cout << "Second";
    return 0;
}

int32_t main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    solve();
    return 0;
}
/*
6
2 1 6 3 4 5
2 1 3 4 5 6
6 0
1 7 8 2 4 6
 * */

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

#define REP(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) REP(i,0,n)
#define INF (1<<30)
#define INFLL (1LL<<62LL)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

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

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  ll Q, H, S, D, N;
  cin >> Q >> H >> S >> D >> N;
  
  ll mp = min(Q * 4, min(H * 2, S));

  if (N == 1) {
    cout << mp << endl;
    return 0;
  }

  ll ans = 0;
  if (N % 2 == 1) {
    ans = mp;
    N--;
  }

  ans += N / 2 * min(mp * 2, D);

  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
	"math"
)

func min(a, b int) int {
	if a >= b {
		return b
	}
	return a
}
func main() {
	var n int
	fmt.Scan(&n)
	a := make([]int, n)
	for i := range a {
		fmt.Scan(&a[i])
	}
	var d, ans int
	ans = math.MaxInt32
	for j := -100; j <= 100; j++ {
		d = 0
		for _, v := range a {
			d += (v - j) * (v - j)
		}
		ans = min(ans, d)
	}
	fmt.Println(ans)
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
#define ll long long
using namespace std;
signed main(){
  ll n,d,x,b,f,z=0;
  ll a[10000];
  cin>>n>>d>>x;
  for(ll i=0;i<n;i++){
    cin>>a[i];
  }
  for(ll i=0;i<n;i++){
    f = 1;
    b = 1;
    while(d>=b*a[i]+1){
      f++;
      b++;
    }
    z += f;
  }
  cout<<z+x<<"\n";
  return(0);
}


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

using namespace std;
typedef struct{
  int hyou;
  int nedan;
  int bangou;
}KYOGI;
main(){
  KYOGI kyogi[1001];
  int n,m,max,min,mdl,sinsa,maxs=0,a,maxes;
  cin>>n;
  cin>>m;
  for(int i=0;i<n;i++){
    cin>>kyogi[i].nedan;
    kyogi[i].bangou=i+1;
    kyogi[i].hyou=0;
  }
  for(int i=0;i<m;i++){
    cin>>sinsa;
    for(int j=0;j<n;j++){
      if(kyogi[j].nedan<=sinsa){
	kyogi[j].hyou=kyogi[j].hyou+1;
	break;
      }
    }
  }
  for(a=0;a<n;a++){
    if(maxs<kyogi[a].hyou){
      maxs=kyogi[a].hyou;
      maxes=a;
    }
  }
  cout<<kyogi[maxes].bangou<<endl;
  return 0;
}
    

Measured memory_bytes: 1172
local n = io.read("n")
local k = io.read("n")
-- local n, k = 1, 1
local g = {[0] = {1, 1}}
for i = 1, n do
	local c0 = g[i - 1][1]
	local p0 = g[i - 1][2]
	local c = c0 * 2 + 3
	local p = p0 * 2 + 1
	g[i] = {c, p}
end
local function f(_n, _k)
	if _k <= 0 then
		return 0
	end
	if _n <= 0 then
		return 1
	end
	local c = g[_n][1]
	local hc = (g[_n][1] + 1) // 2
	if _k >= c then
		return g[_n][2]
	elseif _k == hc then
		return f(_n - 1, _k - 2) + 1
	elseif _k < hc then
		return f(_n - 1, _k - 1)
	else
		return g[_n - 1][2] + 1 + f(_n - 1, _k - hc)
	end
end
print(f(n, k))

Measured memory_bytes: 256
#include <stdio.h>

int main()
{
    int a;
    int b;
    int x;

    scanf("%d %d", &a, &b);

    for(x = 0; x <= 1000; x ++)
    {
        if (a == (int)(0.08 * x) && b == (int)(0.10 * x))
        {
            printf("%d\n", x);
            return (0);
        }
    }
    printf("%d\n", -1);
    return (0);
}

Measured memory_bytes: 128
import java.util.*;

//update 2020/1/1 23:01

public class Main{

  static Scanner sc = new Scanner(System.in);
  static StringBuilder sb = new StringBuilder();

  public static void main(String[] args) {

    int n = nextInt();

    int[][] c = new int[10][10]; //[前][後ろ]

    for(int i=1;i<=n;i++){
      int keta = (String.valueOf(i)).length();
      int aaa = 1;
      for(int j=1;j<=(keta-1);j++){
        aaa *= 10;
      }
      c[i/aaa][i%10] ++;
      //System.out.println("c["+i/aaa+"]["+i%10+"]++");
    }

    int ans = 0;
    for(int i=1;i<10;i++){
      for(int j=1;j<10;j++){
          ans += c[i][j] * c[j][i];
          //System.out.println("ans += c["+i+"]["+j+"]*c["+j+"]["+i+"]");
          //System.out.println("ans += "+((c[i][j]*c[j][i])));
      }
    }




    System.out.println(ans);

  }
  /*
    static String toSmall(String s){
      char c = s.charAt(0);
      //if(Character.isUpperCase(c)){
      if(c<=90){
        c += 32;
      }
      return String.valueOf(c);
    }
    static String toBig(String s){
      char c = s.charAt(0);
      //if(Character.isLowerCase(c)){
      if(c>=97){
        c -= 32;
      }
      return String.valueOf(c);
    }
  */

  static String toSmall(String s){
    return s.toLowerCase();
  }

  static String toBig(String s){
    return s.toUpperCase();
  }

  static String next(){
    return sc.next();
  }

  static int nextInt(){
    return Integer.parseInt(sc.next());
  }

  static long nextLong(){
    return Long.parseLong(sc.next());
  }

  static double nextDouble(){
    return Double.parseDouble(sc.next());
  }

  static String[] splitString(String s){
    return s.split("");
  }

  static char[] splitChar(String s){
    return s.toCharArray();
  }

  static int charToInt(char a){
    return a - 48;
  }

////////////////////////////////////////////
  public static int max(int[] a){
    int lng = a.length;
    int max = a[0];
    for(int i=1;i<lng;i++){
      max = Math.max(max,a[i]);
    }
    return max;
  }
  public static long max(long[] a){
    int lng = a.length;
    long max = a[0];
    for(int i=1;i<lng;i++){
      max = Math.max(max,a[i]);
    }
    return max;
  }
////////////////////////////////////////////

////////////////////////////////////////////
  public static int min(int[] a){
    int lng = a.length;
    int min = a[0];
    for(int i=1;i<lng;i++){
      min = Math.min(min,a[i]);
    }
    return min;
  }
  public static long min(long[] a){
    int lng = a.length;
    long min = a[0];
    for(int i=1;i<lng;i++){
      min = Math.min(min,a[i]);
    }
    return min;
  }
////////////////////////////////////////////

}


Measured memory_bytes: 32468
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

//constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
constexpr long long int MOD = 998244353;
constexpr long double EPS = 1e-8;

long long int N, M, K, L, R, H, W;
//int N, M, K, L, R, H, W;

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

	cin >> N >> M;
	vector<int>v(N);
	for (auto &i : v)cin >> i;
	vector<vector<long long int>>dp(N + 1, vector<long long int>(M + 1));
	for (int i = 0; i < N; i++) {
		if (v[i] <= M)dp[i + 1][v[i]] = i + 1;
		for (int j = 0; j <= M; j++) {
			if (j != M)dp[i + 1][j] += dp[i][j];
			if (j >= v[i])dp[i + 1][j] += dp[i][j - v[i]];
			dp[i + 1][j] %= MOD;
		}
	}
	long long int ans = 0;
	for (int i = 1; i <= N; i++) {
		ans += dp[i][M] * (N - i + 1) % MOD;
	}
	cout << ans % MOD << endl;
}


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

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define a first
#define b second
#define sz(x) (ll)((x).size())
#define pb push_back
#define mp make_pair 
#define bg begin()
#define ed end()
#define all(x) (x).bg,(x).ed
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(ll i=1;i<=n;i++)
#define rrep(i,n) for(ll i=n-1;i>=0;i--)
#define rrep1(i,n) for(ll i=n;i>=1;i--)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
const ll MOD=1000000007;
const ll INF=1000000000000000;

template<class T> inline bool chmin(T& a, T b){if(a>b){a=b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b){if(a<b){a=b;return true;}return false;}
ll maxx(ll x,ll y,ll z){return max(max(x,y),z);}

int main(){
	ll N,W; cin>>N>>W;
	vector<ll> w(N+1);
	vector<ll> v(N+1);
	rep1(i,N){
		cin>>w[i]>>v[i];
	}
	ll dp[110][100100];
	memset(dp,0,sizeof(dp));

	rep1(i,N){
		rep(j,W+1){
			if(j>=w[i]) chmax(dp[i][j],max(dp[i-1][j-w[i]]+v[i],dp[i-1][j]));
			
			chmax(dp[i][j],dp[i-1][j]);
		}	
	}
	cout<<dp[N][W];
}

Measured memory_bytes: 86272
#include <iostream>
#include <stdio.h>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <set>
#include <math.h>
#include <utility>
#include <stack>
#include <string.h>
#include <complex>
using namespace std;
const int INF = 1<<29;
const double EPS = 1e-8;
typedef vector<int> vec;
typedef vector<vec> mat;
typedef pair<int,int> P;
struct edge{int to,cost;};

struct State{
    int d,n,t;
    bool operator<(const State& right) const{
        return d == right.d ? t < right.t : d > right.d;
    }
};

int main(){
    int n, m;
    while(cin >> n >> m, n){
        vector<vector<edge> > g(n);
        for(int i=0;i<m;i++){
            int a, b, c;
            scanf("%d%d%d",&a,&b,&c);
            a--;b--;
            g[a].push_back((edge){b,c});
            g[b].push_back((edge){a,c});
        }

        vector<vec> d(2, vec(n, INF));
        d[1][0] = 0;
        priority_queue<State> que;
        que.push((State){0,0,1});
        while(que.size()){
            State p = que.top(); que.pop();
            if(d[p.t][p.n]<p.d) continue;
            if(p.n==n-1){
                cout << p.d << endl;
                break;
            }
            if(p.t){
                for(int i=0;i<g[p.n].size();i++){
                    int nn1 = g[p.n][i].to;
                    for(int j=0;j<g[nn1].size();j++){
                        int nn2 = g[nn1][j].to;
                        if(d[0][nn2] > p.d){
                            d[0][nn2] = p.d;
                            que.push((State){p.d,nn2,0});
                        }
                    }
                }
            }
            for(int i=0;i<g[p.n].size();i++){
                int nn = g[p.n][i].to, nd = p.d + g[p.n][i].cost;
                if(d[p.t][nn] > nd){
                    d[p.t][nn] = nd;
                    que.push((State){nd,nn,p.t});
                }
            }
        }
    }

    return 0;
}

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

int main() {
  int A, B, C, D;
  cin>>A>>B>>C>>D;
  if(A+B>C+D){
    cout<<"Left"<<endl;}
  if(A+B==C+D){
    cout<<"Balanced"<<endl;}
  if(A+B<C+D){
    cout<<"Right"<<endl;}
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long int dp[101][100001];

long int solve(long int weight[],long int value[],long int w,long int n)
  {
  if(n==0 || w==0)
    return 0;
  if(dp[n][w]!=-1)
    return dp[n][w];
  if(weight[n-1]>w)
    return dp[n][w]=solve(weight,value,w,n-1);
  else if(weight[n-1]<=w)
    return dp[n][w]=max(value[n-1]+solve(weight,value,w-weight[n-1],n-1),solve(weight,value,w,n-1));
}


int main()
{
  long int n,w,i,j;
  cin>>n>>w;
  long int weight[n],value[n];
  for(i=0;i<n;i++)
  {
    cin>>weight[i]>>value[i];
  }
  for(i=0;i<=n;i++)
  {
    for(j=0;j<=w;j++)
    {
        dp[i][j]=-1;
    }
  }
  cout<<solve(weight,value,w,n);
  return 0;
}


Measured memory_bytes: 79104
using System;
using System.Linq;

namespace b
{
    class Program
    {
        static void Main(string[] args)
        {
            var vals = IOUtils.ReadInts();
            var days = vals[0];
            var works = vals[1];
            var daysPerWork = IOUtils.ReadInts();

            var needDays = daysPerWork.Aggregate((a, b) => a + b);
            var restDays = days - needDays;
            Console.WriteLine(restDays < 0 ? -1 : restDays);
        

        }
    }

    static class IOUtils
    {
        public static int ReadInt()
        {
            return int.Parse(Console.ReadLine());
        }
        public static long ReadLong()
        {
            return long.Parse(Console.ReadLine());
        }
        public static ulong ReadUlong()
        {
            return ulong.Parse(Console.ReadLine());
        }
        public static int[] ReadInts()
        {
            return Console.ReadLine().Split(' ').Select(v => int.Parse(v)).ToArray();
        }
        public static long[] ReadLongs()
        {
            return Console.ReadLine().Split(' ').Select(v => long.Parse(v)).ToArray();
        }

        public static void WriteNums(params int[] nums)
        {
            Console.WriteLine(string.Join(" ", nums));
        }
    }
}


Measured memory_bytes: 20400
n, m = [int(e) for e in input().split()]
map_dict = {}
for i in range(n):
    map_dict[str(i+1)] = 0
for _ in range(m):
    cities = [e for e in input().split()]
    map_dict[cities[0]]+=1
    map_dict[cities[1]]+=1
for i in range(n):
    print(map_dict[str(i+1)])

Measured memory_bytes: 3060
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
ll dp[100005][4];
int main() {
  string s;
  int n = s.size();
  cin >> s;
  dp[0][0] = 1;
  for(int i = 0; i < s.size(); i++) {
    for(int j = 0; j <= 3; j++) {
      //i番目の文字に丸をつけるとき
      if(j < 3) {
	if((s[i] == '?') || (j == 0 && s[i] == 'A') || (j == 1 && s[i] == 'B') || (j == 2 && s[i] == 'C')) {
	    dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j]) % mod;
	}
      }
      //i番目の文字に丸をつけないとき
      if(s[i] == '?') {
	dp[i+1][j] = (dp[i+1][j] + (3 * dp[i][j])) % mod;
      }
      else {
	dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % mod;
      }
    }
  }
  
  cout << dp[s.size()][3] << endl;
}
    
	  
  


Measured memory_bytes: 3584
MODE = "stdio"
require 'matrix'

tmp = Array.new

class Integer
  def divisor_list2
    return [1] if self == 1
    (1..Math.sqrt(self).to_i).select do |i|
      self%i == 0
    end.map {|e| [e, self/e]}.flatten.uniq.sort
  end
end

if(defined? MODE)
  tmp = STDIN.read.split("\n")
else
  iotmp = "\
  3 5
  ".split("\n")
  iotmp.each{|s|
    tmp << s.strip
  }
end

a,b = tmp[0].split(" ").map(&:to_i)


print a*b," ",2*a+2*b,"\n"

Measured memory_bytes: 9132
#include <iostream>
#include <string>
#include <cstdlib>	// atoi
#include <stack>
using namespace std;

int main() {
  int a, b;
  stack<int> s;
  string buf;
  while(cin >> buf) {
	if(buf == "+") {
	  a = s.top(); s.pop();
	  b = s.top(); s.pop();
	  s.push(b + a);
	}
	else if(buf == "-") {
	  a = s.top(); s.pop();
	  b = s.top(); s.pop();
	  s.push(b - a);
	}
	else if(buf == "*") {
	  a = s.top(); s.pop();
	  b = s.top(); s.pop();
	  s.push(b * a);
	}
	else {
	  s.push(atoi(buf.c_str()));
	}
  }
  cout << s.top() << endl;
  return 0;
}

Measured memory_bytes: 3152