SPOJ

Problem Link #include <iostream> #include <vector> using namespace std; const int MAXN = 3000; const int MAXPRICE = 1010; long long dp[MAXN][MAXPRICE], albumGreatness[MAXN]; vector<pair<int, int> > album[MAXN]; int main() { int n, m, totalPrice, index; cin >> n >> m  >> totalPrice; int greatness, price, a, albumPrice[m]; for(int i= 0; i < n; i++) { cin >> a >> price >> greatness; //greatness and price of individual song album[a].push_back(make_pair(price, greatness)); albumGreatness[a] += greatness; } for(int i = 1; i <= m; i++) { cin >> albumPrice[i]; } index = 0; for(int i = 1; i <= m; i++) { for(auto songs : album[i]) { index++; for(price = 1; price <= totalPrice; price++) { dp[index][price] = max(dp[index - 1][price], (price >= songs.first) ? dp[index - 1][price - songs.first] + songs.second : 0); } } ...

Problem Link #include <iostream> #include <algorithm> using namespace std; int main() { int t, n, index, count; bool isPossible; cin >> t; while(t--) { cin >> n; pair<int, int> arr[n]; int b[n]; int result[n]; index = 0; isPossible  = true; for(int i = 0; i < n; i++) { cin >> arr[i].first; arr[i].second = i; } sort(arr, arr + n); /* We can have atmost floor(n/2) same colors and still colors of marker and cap can be                             different. If number of same colors > floor(n/2) then atleast one pen will have same                            colored cap. So we are checking if color at position i and i + (n + 1) / 2 position is same                        or no...

Problem Link #include<iostream> #include <algorithm> #include <cstring> using namespace std; int freq[26]; int main() { int t, len, maxFreq, diff, diffa, diffb, ans; string s; cin >> t; while(t--) { cin >> s; memset(freq, 0, sizeof(freq)); len = s.length(); for(int i = 0; i < len; i++) { freq[s[i] - 'A']++; } sort(freq, freq + 26, greater<int>()); ans = len; for(int i = 1; i <= 26; i++) { if(len % i != 0) continue; maxFreq = len / i; diffa = diffb = 0; for(int j = 0; j < i; j++) { if(freq[j] == 0) break; diff = freq[j] - maxFreq; if(diff > 0) { diffa += diff; } else { diffb -= diff; } } ans = min(ans, max(diffa, diffb)); } cout << ans << endl; } return 0; }

Problem Link #include <iostream> using namespace std; int main() { int n, t, dish; long long maxDish; cin >> t; while(t--) { cin >> n; maxDish = 0; while(n--) { cin >> dish; maxDish += (dish - 1); } cout << maxDish + 1 << endl; } return 0; }

Problem Link #include <iostream> #include <vector> #include <cstdio> using namespace std; const int N = 100001; int arr[N]; vector<pair<int, int> > range; int preK[N]; // ith position store number of values equal to k till index i int preK1[N]; // ith position store number of values equal to k + 1 till index i void resetArray() { range.clear();     for(int i = 0; i < N; i++)     {         arr[i] = 0;         preK[i] = preK1[i] = 0;     } } int main() {     int t, n, k, l, r, count, maxCount, maxN, i;     cin >> t;     while(t--)     {         scanf("%d%d", &n,&k);         count = maxCount = maxN = 0;         resetArray();         for(i = 1; i <= n; i++)         {         ...

#include <iostream> #include <vector> #include <cmath> using namespace std ; int pre[ 2005 ][ 2005 ]; int fre[ 2005 ][ 2005 ]; int arr[ 2005 ]; int bsearch ( int i, int j, int k) { int len = j - i + 1 ; int m = ceil (( double )k / len); int mid, pos; m = ceil (( double )k / m); int low = 1 ; int high = 2000 ; while (low < high) { mid = (low + high) / 2 ; pos = (pre[mid][j] - pre[mid][i - 1 ]); if (pos < m) { low = mid + 1 ; } else { high = mid; } } if (low == high - 1 ) { pos = (pre[low][j] - pre[low][i - 1 ]); if (pos >= m) { high = low; } } return high; } void resetArray () { for ( int i = 0 ; i < 2005 ; i++) { arr[i] = 0 ; for ( int j ...

Problem Link #include <iostream> #include <vector> #include <queue> #include <cstdio> using namespace std ; const long INF = 9999999 ; void dijkstra ( int source, long dist[], vector< pair< int , long > > maze[]) { priority_queue< pair< long , int > > pq; dist[source] = 0 ; pq. push ( make_pair ( 0 , source)); int neighbor; long t; while (!pq. empty ()) { int s = pq. top (). second ; pq. pop (); for ( int i = 0 ; i < maze[s]. size (); i++) { neighbor = maze[s][i]. first ; t = maze[s][i]. second ; if (dist[neighbor] > dist[s] + t) { dist[neighbor] = dist[s] + t; pq. push ( make_pair (dist[neighbor], neighbor)); } } } } int main () { int n, exitCell, timer, edges, u, v, t; ...